洛谷P2649 游戏预言（思维 ）

思维 ）"/>

洛谷P2649 游戏预言（思维 ）

原题链接

其实这题我是过了才去想我算法的可行性的（过的一脸懵逼）
我把所有牌分为两部分，一部分是john（a[]）的一部分是对手的(b[])
然后两个sort 从后往前遍历 看是否john必胜必胜的条件：对手最大牌也不能来压john的牌
可能输的条件：对手最大牌用于压john此牌，当然我们会想到一些细节问题，就是每轮对手出
m张牌而john只出1张，怎么能一对一的实现呢？
简单证明如下：
其实对手牌有n*（m-1）张，我们从后往前如果选择了最大一张来压john则再选择m-1张最小的来出
最后这很多的m-1张是不会被遍历到的

#include <iostream>
#include <cstring>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
#include <cstdio>
#include <stdio.h>
#include<queue>
#include<math.h>
#include<stack>
#include<set>
#include<map>
using namespace std;
#define ll long long
inline ll read()
{ll k = 0, f = 1; char ch = getchar();while (ch < '0' || ch>'9'){if (ch == '-')f = -1;ch = getchar();}while (ch >= '0' && ch <= '9'){k = k * 10 + ch - '0';ch = getchar();}return k * f;
}ll a[1005];
ll vis[1005];
ll b[1005];
int main()
{ll m=read(),n=read();for(int i=0;i<n;i++){a[i]=read();vis[a[i]]=1;}sort(a,a+n);ll num=0;for(int i=1;i<=n*m;i++){if(!vis[i]){b[num++]=i;}}sort(b,b+num);ll p=n-1;ll d=num-1;ll ans=0;while(d>=0&&p>=0){if(a[p]>b[d]){ans++;p--;}else d--,p--;}cout<<ans<<'\n';
}