自动搬运

查看原文

来自洛谷，原作者为

	kind_Ygg 这个家伙很懒，什么也没有留下

搬运于2025-08-24 23:05:15，当前版本为作者最后更新于2024-10-19 20:51:29，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

保姆级题解。

题目大意

相信你不是外星人。

思路

最小值最大，一眼二分，三分钟假掉。
正解似乎只能是贪心，我们通过阅读题目可得，我们要操作成一个以 $1$ 为首项，公差为 $1$ 的等差数列，所以首先排序。然后，分两种情况讨论（咱们设当前答案为 $answer$）：

1. $a_i \ge answer$
2. $a_i < answer$

注：下文 $num$ 是可加可不加的，$sum$ 是必须加的。
第一种情况：我们就要将 $a_i$ 变为 $answer$（为了填补序列空缺），所以 $sum$ 加上 $a_i-answer$，由于此时的 $answer$ 已经被填好了，因此 $answer$ 加一。

第二种情况：由于 $a_i < answer$，我们也不能去改变 $a_i$ 的值，所以将 $a_i$ 忽略不计，它无论为何值都不会影响答案（前面的数已经构成了从 $1$ 到 $answer-1$ 的等差数列，这就代表 $[1,answer-1]$ 的数都有了，而 $a_i$ 只能比它本身小），但它本身又可以为答案产生贡献，所以 $num$ 加上 $a_i-1$（$-1$ 是因为题目说不能删完）。

最后，如果 $ans$ 在 $[sum,sum+num]$ 中，就代表可以填补 $ans$ 这个空缺，所以 $answer+1$。

Code

#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int N=1e5+5;
int T,n,a[N];
signed main()
{
	cin>>T;
	while(T--)
	{
		cin>>n;
		for(int i=1;i<=n;i++) cin>>a[i];
		sort(a+1,a+n+1);
		int ans=1;
		int num,sum;
		num=sum=0;
		for(int i=1;i<=n;i++)
		{
			if(a[i]>=ans) sum+=a[i]-ans,ans++;
			else num+=a[i]-1;
		}
		if(sum<=ans and sum+num>=ans) ans++;
		cout<<ans<<'\n';
	}
	return 0;
}

后话

这题的贪心策略有些复杂，但只要想到了就秒切。
祝各位 OIer 们 CSP/NOIP RP++。