题目描述 公司举办团建活动，许多人在一起玩一个纸牌游戏。规则如下： 总共有 n 个人，每个人初始有 n 张牌。每一轮从第一个人开始轮流操作，第 i 个人每次操作必须选择 m i n ( p e o p l e − 1 , a i ) min(people-1,a_i) min(people−1,ai)个不同的人，分别从他们手中拿走一张牌。其中 p e o p l e people people 为游戏现存人数，手上没有牌的人立即被淘汰出局。大家希望有尽可能多的人出局，游戏无限的进行下去，问最终游戏中最少还有几个人没有出局。 注意：不能从自己手中拿牌。
输入描述: 第一行输入一个数字 n n n， 代表游戏的总人数。接下来输入 n n n 个数字，分别代表 a i a_i ai 输出描述: 输出一行一个整数表示游戏最终最少剩几个人。
输入 2 1 2
输出 2
说明 两个人只能互相拿对方的一张牌，游戏永远进行下去。 备注: 对于 20 20 20% 的数据，满足 n ≤ 2 n≤2 n≤2； 对于 40 40 40% 的数据，满足 n ≤ 3 n≤3 n≤3； 对于 100 100 100% 的数据，满足 1 ≤ n ≤ 1 0 5 , 1 ≤ a i ≤ 1 0 9 1≤n≤10^5,1≤ a_i ≤10^9 1≤n≤105,1≤ai≤109
解题思路 题目中交代每个人希望有尽多的人会出局，所以可以想到每个人都会拿每回合增长数最小的那个人的牌，因为所有人的初始手牌都是相同的，增长数最少的人便是最容易出局的。 这时我们可以想到首先按照每回合拿牌数量进行一次排序，设每个人的位置为 i （ 1 < = i < = n ） i（1<=i<=n） i（1<=i<=n），那么当所有人优先拿他的牌的时候，证明他的左侧已经没有其他人了，所以他每回合会被剩下的 n − i n-i n−i个人拿走 n − i n-i n−i张纸牌。 这时分两种情况：如果 a i > = n − i ai>=n-i ai>=n−i,那么他每回合可以从剩下 n − i n-i n−i个人手里拿 a i − ( n − i ) ai-(n-i) ai−(n−i)张牌，成为平衡状态，游戏可以持续进行，则最小剩余人数就是 n − i + 1 n-i+1 n−i+1；如果 a i < n − i ai<n-i ai<n−i，那么他每回合失去的牌要大于能拿回的牌，必定会出局，此时判断第 i + 1 i+1 i+1个数。
代码
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<queue> using namespace std; int n,a[110000]; int main(){ scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); sort(a+1,a+n+1); for(int i=1;i<=n;i++) { if(a[i]>=n-i) { printf("%d",n-i+1); return 0; } } }