CF1633C题解

__vector__ · 2022-02-04 20:10:22 · 题解

题目意思：

一个角色与怪物决斗。
角色有以下两个属性：
1.hc：生命值
2.dc：攻击力
怪物有以下两个属性：
1.hm：生命值
2.dm：攻击力

决斗方式：
1.角色向怪物发动攻击，怪物生命值掉了 dc。
2.怪物向角色发动攻击，角色生命值掉了 dm。
如此循环，直到其中一方的生命值小于等于 0，另一方获胜。

决斗开始之前，角色可以购买装备，角色有 k 枚硬币，一个硬币可以使生命值增加 a，也可以使攻击力增加 w。
求如果以最优的方式购买装备，角色是否能打败怪物。

有 t 组数据，1 \le t \le 5 \cdot 10^4。

题目分析：

看到这道题，可以发现测试数据组数很多，可能需要 O(1) 回答每组询问，但是，既然是要求最优方案，难以做到 O(1) 回答询问。
此时可以发现，题目里面说了，所有测试数据的 k 之和不超过 2 \cdot 10^5。所以直接枚举分配给生命值和角色的硬币数量，对于枚举到的每组方案显然可以 O(1) 判断角色是否可以胜利，如果可以胜利输出 YES，如果所有方案都不可行输出 NO。（我到比赛结束前十几分钟才发现这个最后没时间写了） 这道题就做出来了。

注意事项：

如果就这样写，将会在第 13 个测试点 WA 掉，原因是神仙 hacker 造的数据会爆掉 long long，所以在 C++20 下开 __int128 即可。

AC代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(!isdigit(ch))
    {
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(isdigit(ch))
    {
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}
int t;
signed main()
{
    scanf("%lld",&t);
    int hc,dc,hm,dm,k,w,a;
    while(t--)
    {
        scanf("%lld%lld",&hc,&dc);//角色的生命和攻击力
        scanf("%lld%lld",&hm,&dm);//怪物的生命和攻击力
        scanf("%lld%lld%lld",&k,&w,&a);
        bool flag=0;
        for(int i=0;i<=k;i++)
        {
            int gjl=(k-i)*w+dc;//新的攻击力
            int sd=hm/gjl-1;//杀死怪物时受到伤害的次数
            if(hm%gjl>0)sd++;
            if((__int128)hc+(__int128)i*(__int128)a>(__int128)sd*(__int128)dm)
            {
                printf("YES\n");
                flag=1;
                break;
            }
        }
        if(!flag)printf("NO\n");
    }
    #ifndef ONLINE_JUDGE
    system("pause");
    #endif
    return 0;
}