自动搬运

查看原文

来自洛谷，原作者为

	ys_kylin__ 切

搬运于2025-08-24 22:48:34，当前版本为作者最后更新于2023-07-18 08:15:59，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

首先，我们一看这道题，数据范围整整 $10^6$，那就不可能用枚举了，然后思考一下，我能修改 $k$ 个数，那肯定是每一次都挑选最大的，可是由于当前的最大数是实时更新的，不可能慢慢找。于是我们便找到了办法：二分！

二分的时间复杂度是 $O(n \log n)$，而 $10^6$ 刚刚好不会爆。

我们需要每次二分一条“众数线”设为 $mid$，即当一个数出现的次数大于等于 $mid$ 时，他便可能成为众数。

那 check 怎么写这个问题，就简单多了。

每次的 $x$ 首先加 $k$（因为无论选择哪个，最终 $mid$ 都会加 $k$），然后遍历计数数组（计算每个数出现的次数），如果发现大于 $x$，就把多出来的部分记下，最后把记下的数与 $k$ 比较就行了。

注意一下，若最后二分出的数为零，输出正无穷（也就是 pigstd）。

好了，直接上代码（赛时写的比较丑，见谅）。

#include<bits/stdc++.h>
using namespace std;
int a[1000005],vis[1000005];
int n,k,maxa=0;//maxa为原数组中众数出现的次数
int mp[1000005];//用来存每个数出现的次数
//特殊说明：用map会TLE,int就行
int check(int x) {
	memset(vis,0,sizeof vis);
	x+=k;
	long long m=0;
	for(int i=1;i<=n;i++) {
		if(mp[a[i]]>x && vis[a[i]]==0) {
			vis[a[i]]=1;
			m+=mp[a[i]]-x;
		}
	}
	if(m>k) return 0;
	else return 1;
}
int main() {
	int ans=0;
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++) {
		scanf("%d",&a[i]);
		mp[a[i]]++;
		maxa=max(mp[a[i]],maxa);
	}
	if(k>=maxa) {//并无意义，只是为了方便
		printf("pigstd");
		return 0;
	}
	int l=0,r=1000000,mid;
	while(l<r) {//二分
		mid=(l+r)>>1;
		if(check(mid)) {
			r=mid;
		}
		else {
			l=mid+1;
		}
	}
	if(l==0) {
		printf("pigstd");
		return 0;
	}
	for (int i=1;i<=1e6;i++)
		if(mp[i]>=l) ans++;
	printf("%d",ans);
   return 0;
}