【题解】 洛谷 P2649 游戏预言

题目：

p2649 游戏预言

题意：

john和他的好朋基友们在van纸牌游戏。共有$m$个人。纸牌有$n \times m$张，从$1……n \times m$编号。每人有$n$张。每人一回合出一张牌，编号最大的获胜。由于输了有蜜汁惩罚，john想尽可能地多赢。（欲知后事如何，且听下回分解。。。

思路：

题目问的是john最少赢多少次。我们可以设想：john十分美味多汁。他的好朋基友们都想让他接受蜜汁惩罚所以合伙坑john。这样我们可以将不是john的牌放到一堆。每当john出一张牌就先出一张比该牌大的且不是john的的牌。然后剩余的$m-2$张牌就从小的挨着出。直到出够$m-2$张。如果没有比john的牌大的john必赢

$code$

#include<iostream>
#include<cstring>
#include<string>
#include<cstdio>
#include<algorithm>
#define rr register
int ans,n,m,sum,jcard[51];
bool vis[1010],used[1010];

inline void read(int &t) {
    int x=0;bool f=0;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=!f;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    t=f?-x:x;
}

int main() {
    read(m),read(n);
    for(rr int i=1,a;i<=n;++i) {
        read(a);
        vis[a]=1;
        jcard[++sum]=a;
    }
    for(rr int i=1;i<=sum;++i) {
        int num=m-1;
        int x=jcard[i];
        used[x]=1;
        for(rr int j=x+1;j<=n*m;++j) {
            if(!used[j]&&!vis[j]) {
                num--;
                used[j]=1;
                break;
            }
        }
        if(num==m-1) ans++;
        for(int j=1;num>0;++j) {
            if(!used[j]&&!vis[j]) {
                num--;
                used[j]=1;
            }
        }
    }
    std::cout<<ans<<'\n';
    return 0;
}

月考rp++