题解 P2649 【游戏预言】

· · 题解

其实这题的代码难度很低的，但是要想到又快又好的算法并不容易。

首先为了方便，我们假设John总是把牌从大到小出。（有点田忌赛马的意思233）

然后我们可以认为，其余所有的牌都拿在一个人手里。如果已经能够赢得这一轮，剩下要出的牌拿最小的占位即可。

之后我们从大到小枚举每一张牌。对于i号牌：

①它是对（lao）方（qian）手上的牌。此时我们把它拿进手牌里。

②它是John手上的牌。此时，如果手上的储备牌足够（至少有1张能够压住John），那么我们总是应该选择压上。道理非常明显：对于一张对手的牌，无论盖上了John的哪一张牌，它为对手创造的收益都是1。如果这张压了，会让John赢得的轮数减少1；如果这张牌不压John，那么最好的情况就是它在后面的时候派上了用场，轮数还是减少1（如果悲剧一点，后面它就成了赘余牌，收益只有0）。“好钢要用在刀刃上”，就是这个道理。所以，我们的贪心策略是：“能压就压”。

具体到代码上，我们用桶排存下John的每一张牌，从m*n到1反向枚举，如果是对手的牌则加入储备牌库（直接cnt++就行）；是John的牌就看看牌库有没有牌，有的话cnt--，没有的话ans++。

仅19行的代码如下：

#include <iostream>
#include <cstdio>
using namespace std;
int a[51],b[1001],n,m,cnt,ans;
int main()
{
    scanf("%d%d",&m,&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        b[a[i]]=1;
    }n*=m;
    for(int i=n;i>=1;i--){
        if(!b[i])++cnt;
        else if(cnt>0)--cnt;
        else ++ans;
    }
    printf("%d",ans);
    return 0;
}