D 纯n^2做法

一个纯 $n^2$ 的做法。

首先统计出每个值 $x$ 出现的次数 $cnt_x$ 。我们按照 $cnt_{x}$ 从大到小排序，如果 $cnt$ 相同就比较 $x$ 的大小关系。这样排在第一个的就是众数，第二的就是众数的“第二候选人”，一次类推。我们只需要保留前 $5$ 个就行了。

现在假设我们让 $a_i-1$ 然后让 $a_j+1$ ，考虑现在众数是什么。令 $p,q,r,s$ 为 $a_i,a_i-1,a_j,a_j+1$ ，那么我们新的众数只需要在预处理的“众数前五候选人”和 $p,q,r,s$ 中选出最好的那个就可以了。

证明：对于没有变动过的数，他们肯定打不过前五候选人中的任意一个。而我们只会变动四个数，所以前五候选人肯定存在一个没有变动过的数。

代码：

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
using namespace std;
#define int long long
const int mxn=1e6+6;
int a[1003],n,cnt[mxn],ok[mxn];
int mx=0,cmx=0,cans;
int nt=-1111111,cat;
int qry[mxn];
vector<pair<int,int> >bsts;
void go(int i,int j){
	int p=a[i],q=a[i]-1,r=a[j],s=a[j]+1;
	--cnt[p],++cnt[q];
	--cnt[r],++cnt[s];
	int mx=0,ans=0;
	for(auto ee:bsts){
		int x=ee.second;
		if(x==p or x==q or x==r or x==s)continue;
		if(ee.first>mx){
			mx=ee.first;
			ans=ee.second;
		}else if(ee.second==mx)ans=max(ans,ee.first);
	}
	if(cnt[p]>mx){
		mx=cnt[p];
		ans=p;
	}else if(cnt[p]==mx)ans=max(ans,p);
	if(cnt[q]>mx){
		mx=cnt[q];
		ans=q;
	}else if(cnt[q]==mx)ans=max(ans,q);
	if(cnt[r]>mx){
		mx=cnt[r];
		ans=r;
	}else if(cnt[r]==mx)ans=max(ans,r);
	if(cnt[s]>mx){
		mx=cnt[s];
		ans=s;
	}else if(cnt[s]==mx)ans=max(ans,s);
	++cnt[p],--cnt[q];
	++cnt[r],--cnt[s];
	ok[ans]=1;
}
inline void solve(){
	cin>>n;
	for(int i=1;i<=n;++i)cin>>a[i],++cnt[a[i]];
	for(int i=0;i<mxn;++i)bsts.push_back({cnt[i],i});
	sort(bsts.rbegin(),bsts.rend());
	while(bsts.size()>5)bsts.pop_back();
	for(int i=1;i<=n;++i){
		for(int j=1;j<=n;++j){
			if(i==j)continue;
			go(i,j);
		}
	}
	for(int i=0;i<mxn;++i)if(ok[i])cout<<i<<' ';cout<<'\n';
}
signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int T=1;
	//cin>>T;
	for(;T--;)solve();
	return 0;
}