题意:
有n个大小为n的数,第i个数每回合会增长ai,同时有ai个数会减小1,问最多有多少个数可以持续存在。
分析:
题目中交代每个人希望有尽多的人会出局,所以可以想到每个人都会拿每回合增长数最小的那个人的牌,因为所有人的初始手牌都是相同的,增长数最少的人便是最容易出局的。
这时我们可以想到首先按照每回合拿牌数量进行一次排序,设每个人的位置为i(1<=i<=n),那么当所有人优先拿他的牌的时候,证明他的左侧已经没有其他人了,所以他每回合会被剩下的n-i个人拿走n-i张纸牌,这时分两种情况:如果ai>=n-i,那么他每回合可以从剩下n-i个人手里拿n-i张牌,成为平衡状态,游戏可以持续进行,则最小剩余人数就是n-i+1;如果ai<n-i,那么他每回合失去的牌要大于能拿回的牌,必定会出局,此时判断第i+1个数。
代码:
#include<iostream> #include<cstring> #include<cstdio> #include<queue> using namespace std; int n,a[100010],m; int main() { scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); } sort(a+1,a+1+n); for(int i=1;i<=n;i++) { if(a[i]>=n-i) { printf("%d",n-i+1); break; } } return 0; }