2020牛客暑期多校训练营（第十场）D-Hearthstone Battlegrounds

题目大意

没玩过炉石的小白翻译：
现在有四种随从，这里的每种随从，如果对面没有免疫都是秒杀：

• 带圣盾、亡语；
• 带圣盾；
• 带亡语；
• 普通随从。

每种buff的效果：

• 圣盾效果：免疫任何攻击，免疫一次后消失；
• 亡语效果：随从死亡时召唤一个藤蔓；
• 藤蔓：只有1攻击1血量的小怪。

每回合都要发动一次攻击，游戏结束时还有随从存活就算获胜（平局不算获胜）。
幸运的是，你掌握着你的对手(?)，只要有一点可能获胜就可以赢。
现在你有a[i]个i种随从，他的对手有b[i​]个i种随从，你能否获胜？

解题思路

不要被原题的长长长长长描述劝退，因为我们操控着对手，可以让对面应付我们的最优策略，所以这道题很显然是贪心策略的问题。那么我们开始以上帝视角分析：

• 藤蔓没法干掉任何随从（普通随从血量都是10^9），所以，藤蔓只能优先用来破圣盾；
  而反过来让对方下得一首烂棋，直接用对面的藤蔓打这边没有盾的随从白给即可。

• 没有藤蔓后，直接用圣盾刚当然血亏。所以，我们让带亡语的先上，留下藤蔓破对面圣盾。

• 以上都用完后，我们再最后上第一种满buff的随从，圣盾保护+制造藤蔓。

• 藤蔓苟到最后也是一种方法，所以召唤的藤蔓要尽可能多。

AC代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5+10,M=1e9;
int T,a1,a2,a3,a4,a5,b1,b2,b3,b4,b5;
void fight()
{
    if(b3) b3--,b5++;
    else if(b4) b4--;
    else if(b1) b1--,b3++;
    else b2--,b4++;
}
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        a5=b5=0;
        scanf("%d%d%d%d%d%d%d%d",&a1,&a2,&a3,&a4,&b1,&b2,&b3,&b4);
        while(a1+a2+a3+a4 && b1+b2+b3+b4)
        {
            if(a3+a4) b5=0;
            if(a5 && b1+b2)
            {
                if(b1) b1--,b3++;
                else b2--,b4++;
                a5=0;
            }
            if(a3) a3--,a5++;
            else if(a1) a1--,a3++;
            else if(a2) a2--,a4++;
            else a4--;
            fight();
        }
        if(b1+b2+b3+b4 || !(a1+a2+a3+a4) && a5<=b5) puts("No");
        else puts("Yes");
    }
}