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