题意
给一个n个数的数列a，a[i]<=n
定义一个操作：每次可以交换任意位置的两个值；
定义最优操作:对于任意一个原数列的一组排列，使其通过尽可能少的操作变回原数列；
求构造一组原数列的一组排列，使得在最优操作下操作次数尽可能多；
一开始读，都错题了，读成交换智能交换相邻点，一直在考虑逆序对，终于写出来了以后，一直wa，才发现原来是任意点交换
提示
1. 考虑每个点的值没有重复的话，那么很简单，直接构建一个环就好了，操作次数N-1
2. 考虑到有两个相同数值的在一个环里的话，那么就可以分裂成两个环，这样最优解的个数就能减一
3. 因此只需要每次构建一个环，把所有数值的点每次囊括进去一个，直到没有环就好了
#include<bits/stdc++.h>
using namespace std;
vector<int> G[200005];
int a[200005], b[200005];
void run() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
G[i].clear();
}
for (int i = 1; i <= n; i++) {
int x;
cin >> x;
a[i] = x;
G[x].emplace_back(i);
}
set<int> cnt;
for (int i = 1; i <= n; i++) {
if (G[i].size())cnt.emplace(i);
}
int sum = 0;
while (sum < n) {
vector<int> now, u;
for (auto k: cnt) {
now.emplace_back(G[k].back());
G[k].pop_back();
if (G[k].size() == 0) {
u.emplace_back(k);
}
}
sum += now.size();
for (int i = 0; i < now.size() - 1; i++) {
b[now[i + 1]] = a[now[i]];
}
b[now[0]] = a[now[now.size() - 1]];
for (auto k: u)cnt.erase(k);
}
for (int i = 1; i <= n; i++)cout << b[i] << " \n"[i == n];
}
int main() {
int t;
cin >> t;
while (t--)
run();
return 0;
}