自动搬运

查看原文

来自洛谷，原作者为

	Fat_Fish ⁡

搬运于2025-08-24 22:31:16，当前版本为作者最后更新于2021-05-04 21:20:24，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

对于这样一个数列，我们可以先$sort$排序一遍，求出最小的第一名$b_n+1$,如果$B_i+n>B_n+1$,答案$ans++$即可

$Code$

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
const int maxn=3e5+10;
int a[maxn];
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n,ans=0;
	cin>>n;
	for(int i=1;i<=n;++i){
		cin>>a[i];
	}
	sort(a+1,a+1+n);
	for(int i=1;i<=n;++i){
		if(i==n){
			++ans;
			break;
		}
		if(a[i]+n>=a[n]+1){
			++ans;
		}
	}
	cout<<ans<<'\n';
	return 0;
}

欢乐的爆零了。原来是因为如果出现有重复数据的情况下，$B_n+1$不一定是最大值,只需循环一遍求出最大值即可，注意:使第一名的人尽可能多，就要让最大值尽可能小。即$a_i+n-i+1$为最优。

$Code$

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
const int maxn=3e5+10;
int a[maxn];
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);//读入优化，速度媲美scanf
	int n,ans=0;
	cin>>n;
	for(int i=1;i<=n;++i){
		cin>>a[i];
	}
	sort(a+1,a+1+n);//从小到大一遍排序
	int mx=INT_MIN/3;//初始化一个很小的数，/3防溢出（好习惯，在此无用）
	for(int i=1;i<=n;++i){
		mx=max(mx,a[i]+n-i+1);//尽可能使最大值最小
	}
	for(int i=1;i<=n;++i){
		if(a[i]+n>=mx){
			++ans;//超过最大值，累加
		}
	}
	cout<<ans<<'\n';//完美输出！
	return 0;
}