自动搬运

查看原文

来自洛谷，原作者为

	Weslie 梦与奇迹游乐场

搬运于2025-08-24 23:02:33，当前版本为作者最后更新于2024-08-24 21:52:04，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

一个小清新贪心题。

思路

发现删数的操作等同于把 $a_h$ 去掉，其他不变。

因为第 $i$ 轮一定删掉了 $i$ 个数，所以实际上我们下一次访问的下标是 $a_h+i$。

接下来我们对 $a$ 排序（升序）。

一共有 $n$ 个数，所以如果这一轮 $i$ 游戏不结束，我们最多可以选最后一个小于等于 $n-i$ 的数。

接着就是一个贪心策略：我们选最后一个小于等于 $n-i$ 的数。

证明：因为现在选的这个数在下一轮不一定可以使用，但是比这个数更小的数或许可以。所以先把这一个拉上去，留着更小的以后使。

不难发现我们肯定可以构造一个初始序列使得操作按上面的贪心策略进行。

实现起来，可以二分，也可以使用线性做法。

线性做法是基于一个定理：如果 $a$ 是升序排序的，且 $a_i+x\le n$ 是对于第 $x$ 轮的最大的 $a_i$，则使 $a_j+x+1\le n$ 的最大的 $a_j$ 一定满足 $j<i$。显然如果 $j>i$，$a_j>a_i$，就会有 $a_j+x+1>a_i+x>n$。

代码

#include<bits/stdc++.h>
using namespace std;
int T,n,a[500005],ans;
int main(){
	scanf("%d",&T);
	while(T--){
		scanf("%d",&n);
		for(int i=1;i<=n;i++){
			scanf("%d",&a[i]);
		}
		sort(a+1,a+n+1);
		int t=n;
		ans=1;
//		a[0]=-2147483647;
		for(int i=n;i>=1;i--){
			if(a[i]+ans<=n)ans++;
		}
		printf("%d\n",ans);
	}
	return 0;
}