我们知道要是任意位置交换就是环长-1
那我们肯定要让环尽量少即可
那我们的环最多就是 出现最多的那个数字的 次数
构造策略 就是把其他不同的数字 都提出来 然后往后挪一下就可以构造出环了
void solve(){
int n;cin>>n;
vector<int>a(n+1),v[n+1];
for(int i=1;i<=n;i++){
cin>>a[i];
v[a[i]].push_back(i);
}
vector<pair<int,vector<int>>>b;
for(int i=1;i<=n;i++){
if(v[i].size()){
b.push_back({v[i].size(),v[i]});
}
}
sort(all(b),greater<>());
while(b[0].first) {
vector<int>d;
for (auto &[sz, v]: b) {
if (sz == 0)break;
d.push_back(v.back());
v.pop_back();
sz--;
}
for(int i=1;i<d.size();i++){
swap(a[d[i-1]],a[d[i]]);
}
}
for(int i=1;i<=n;i++)cout<<a[i]<<' ';cout<<endl;
}