题解 CF1296D 【Fight with Monsters】

(Solution)
首先我们不难发现这道题其实就是一道贪心+排序的题。但是如何贪心呢？我首先想到的是将每个怪物的生命值取余 (a+b) 然后在拿一个数组记录每个怪物需要用几次特殊的手段，最后再循环判断累加即可。但是这里出现了一个问题，如果一个怪物的生命值刚好取余 (a+b=0) 那该怎么办？想了好久，我终于想到了一种办法，在每次取余的时候，将那个怪物的生命值减去 (1) 再取余。用这样的方法就可以 (AC) 了。

(code)

#include<bits/stdc++.h>
//这次用了万能头文件，因为不只有cstdio了(大雾弥漫）
using namespace std;
inline int read()//快速读入
{
    int x=0,k=1;char c=getchar();
    while(c<'0' || c>'9'){if(c=='-') k=0;c=getchar();}
    while(c>='0' && c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return k?x:-x;
}
int n,a,b,k,x,cost[200010],ans;
//cost 数组就是记录该怪物需要用多少次特殊的手段才能让自己得分
int main()
{
    n=read(),a=read(),b=read(),k=read();//输入
    for(int i=0;i<n;i++)
    {
        x=read();//输入每个怪物的生命值
        x=(x-1)%(a+b);//用上述方法取余 a+b
        cost[i]=x/a;//记录次数
    }
    sort(cost,cost+n);//将次数排序，从小到大依次判断
    for(int i=0;i<n;i++)
    {
        k-=cost[i];
        //将可以使用特殊手段的次数减去当前怪物需要用的次数
        if(k<0) break;
        //如果小于 0 就说明这个怪物你打不死了，所以直接跳出循环
        ans++;//计数器++
    }
    printf("%d",ans);//输出
    return 0;
}