题目中

你需要求出有多少整数可能成为 $b$ 的众数。

想表达的意思应该是

你需要求出有多少种数可能成为 $b$ 的众数。

吧。

所以你输出的是能成为众数的种类数，而不是个数。

解法：

这里我提供一种贪心的做法。

首先只需维护出每一种数出现的次数（因为题目只关心可能成为众数的数的数量）。

接下来我们思考怎样一种数才可能成为众数。

经过 $k$ 次修改以后，一种数只有在被修改后出现次数大于等于被修改后出现次数最大的那种数的出现次数时才可以成为众数。

那么每一次修改是什么呢？

想要让第 $i$ 种数成为众数，对于每一次修改，我们将除了第 $i$ 种数外的一个数修改为第 $i$ 种数。这样就让第 $i$ 种数出现的次数 $+1$ ，让除了第 $i$ 种数外的一种数出现的次数 $-1$ 。不难想到，这样可以让第 $i$ 种数出现的次数最大。

具体来说，设第 $i$ 种数出现的次数为 $v_i$ ，那么它在被操作 $k$ 次后出现的次数为 $v_i+k$ ，设经过操作后的最大出现次数为 $x$ ，那么第 $i$ 种数能成为众数的条件是：

$$v_i+k \geq x$$

因为 $v_i+k$ 已经确定了，所以想让成为众数的数尽可能多，就要让 $x$ 最小。

怎么让 $x$ 最小呢？

我们让当前一个最大的出现次数 $-1$ ，然后把它放回原数列，再找到当前一个最大的出现次数，如此操作 $k$ 次就可以了。

比如一个数组 $v=[1,2,3,5,4,3]$ ，经过 $5$ 次操作后的状态如下：

第一次操作：

$$[1,2,3,4,4,3]$$

第二次操作：

$$[1,2,3,3,4,3]$$

第三次操作：

$$[1,2,3,3,3,3]$$

第四次操作：

$$[1,2,2,3,3,3]$$

第五次操作：

$$[1,2,2,2,3,3]$$

由于每次都要取出其中的最大值，所以这个问题刚好可以用大根堆（优先队列）来解决。每次操作取出堆顶，将其 $-1$ ，然后丢回堆里面。

核心代码如下：

1
2
3
4
5
6
7
8
9
10
priority_queue<int>q;
for(int i=1;i<=tot;i++){
	q.push(v[i]);
}
while(k--){
	int tmp=q.top()-1;
	q.pop();
	q.push(tmp);
}
tmp=q.top();

由于堆每次操作的复杂度为 $O(\log n)$ ，$k$ 次操作的复杂度就是 $O(k \log n)$ ，也就是 $O(n \log n)$ ，在 $10^6$ 的数据下可以通过。

最后一个问题，怎么处理无限多种数可以成为众数的情况？

如果经过操作后的最大出现次数 $x \leq k$ 时，也就是说任意一个数操作 $k$ 次都能修改成众数，自然答案就是无限了。

代码如下（写的不太好）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include<bits/stdc++.h>
#define int long long
using namespace std;
int cnt[1919810],v[1919810];
priority_queue<int>q;
int n,k,tot;
signed main(){
	cin>>n>>k;
	int vk=k;
	for(int i=1;i<=n;i++){
		int x;
		cin>>x;
		cnt[x]++;
	}
	for(int i=1;i<=n;i++){
		if(cnt[i])v[++tot]=cnt[i];
	}
	for(int i=1;i<=tot;i++){
		q.push(v[i]);
	}
	int mx=q.top();
	while(k--){
		int x=q.top()-1;
		q.pop();
		q.push(x);
	}
	int ww=q.top(),ans=0;
	if(ww<=vk){
	    cout<<"pigstd"<<endl;
	    return 0;
	}
	for(int i=1;i<=tot;i++){
		if(v[i]+vk>=ww){
			ans++;
		}
	}
	cout<<ans<<endl;
	return 0;
}