题解：P11205 「Cfz Round 9」Hope

· · 题解

保姆级题解。

题目大意

相信你不是外星人。

思路

最小值最大，一眼二分，三分钟假掉。
正解似乎只能是贪心，我们通过阅读题目可得，我们要操作成一个以 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++。