题解 | #小红打怪#
小红打怪
https://ac.nowcoder.com/acm/problem/254195
不是最优解
这道题主要是处理每一个怪物要攻击几次才能击杀，又会对小红造成多少伤害，所以肯定要先击败对小红造成伤害少的怪物
只需要一个for循环，先记录小红第n次攻击能造成多少伤害，用数组a[]记录这里下标从0开始，因为第n次击杀小怪只会收到n-1次攻击，所以下标从0开始，代表为n才击杀，则小红也会被攻击n次
每隔两次普通攻击是一次强化攻击，所以a[0]=2,a[1]=3,a[2]=4,a[3]=5.....
然后判断a[i]是不是大于小怪血量，如果是记录小怪会对小红造成的伤害，b[ ]存入小怪攻击力，b[ ] * i 就是小怪会对小红造成的伤害，可以用二分也可以顺序枚举写。
然后对 b[ ] 排序，在判断小红最多能击杀多少怪物
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=110000;
ll a[N],b[N];
int main()
{
a[0]=2; //第一次为强化攻击，后面每两次普通攻击过后，也就是对3求余为0时为强化攻击
for(int i=1;i<N;i++)
{
if(i%3==0)a[i]=a[i-1]+2;
else a[i]=a[i-1]+1; //存下小红第i+1次攻击的伤害
}
ll n,q,h,k,x;
ll p1,p2;
scanf("%lld%lld%lld",&n,&h,&k); //怪物数量，初始血量，回血量
for(int i=1;i<=n;i++)
{
scanf("%d%d",&p1,&p2);
ll p3;
for(int i=0;i<N;i++)
{
if(a[i]>=p1) //计算小红第几次能消灭怪物
{
p3=i;
break;
}
}
b[i]=p3*p2; // 计算小怪会对小红造成的伤害
}
sort(b+1,b+n+1); // 排序，优先击败对小红造成伤害少的小怪
scanf("%lld",&q);
while(q--)
{
scanf("%lld",&x);
ll s=h+x*k; //计算小红血量上限
ll cnt=0,sum=0;
for(int i=1;i<=n;i++)
{
sum+=b[i];
if(sum<s) //判断小红能否在死亡前击杀小怪，如果小红死了，就break;
cnt++;
else
break;
}
cout<<cnt<<" "; //cnt就是击杀小怪数量
}
return 0;
}
投递美团等公司10个岗位