纸牌游戏

题目

公司举办团建活动，许多人在一起玩一个纸牌游戏。规则如下： 总共有 n 个人，每个人初始有 n 张牌。每一轮从第一个人开始轮流操作，第 i 个人每次操作必须选择 min(people-1,a_i)min(people−1,ai)个不同的人，分别从他们手中拿走一张牌。其中people 为游戏现存人数，手上没有牌的人立即被淘汰出局。大家希望有尽可能多的人出局（友善.txt），游戏无限的进行下去，问最终游戏中最少还有几个人没有出局。 注意：不能从自己手中拿牌

输入

第一行输入一个数字n，代表游戏的总人数。接下来输入n个数字，分别代表ai

输出

输出一行一个整数表示游戏最终最少剩几个人。

Sample Input

2 1 2

Sample Output

2

解析

只能互相拿一张牌，游戏永远进行下去。

数据

1（别问我为什么有1，我也不知道）<=n<=1e5（核平），1<=ai<=1e9

---

丝毫不懂就开始动手写了一个暴力模拟 30~40分……（备注：这四个点n<=3） 随手重构一波 意外AC（香啊） 其实攻击可以理解为“吸血”（友好团队），直接从大到小快排，然后从n到2循环，每次判断他能不能把i-1个人都吸血，如果可以，输出这个人的编号（剩下这些人都活了下来）并结束程序

code:

#include<iostream> #include<algorithm> using namespace std; int n,a[100001],maxn=0,s=0; bool cmp(int a,int b) { return a>b;//必加 } int main() { cin>>n; for(int i=1;i<=n;i++) { cin>>a[i]; a[i]=min(a[i],n-1);//日常憨憨 } sort(a+1,a+n+1,cmp); for(int i=n;i>=2;i--)//其实1也行 { a[i]=min(a[i],i-1);//憨憨*2 if(a[i]==i-1)//抗伤能力 { cout<<i; return 0; } } return 0; }