Codeforces Global Round 20--F1

F1. Array Shuffling

结论

交换的次数=点数-循环圈的数量
所以只需要构造尽量多的循环圈，圈上的各个元素都是不相同的就可以了。

代码

#include <bits/stdc++.h>
using namespace std;
using pii=pair<int,int>;
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define TT int _=read();while(_--)
#define endl '\n'
const int M=2e5+5;

inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    return x*f;
}

inline void print(int x) {
    if(x<0){putchar('-');x=-x;}
    if(x/10)print(x/10);
    putchar(x%10+'0');
}
//二分不要乱用边界
int a[M],b[M];
vector<int>g[M];

signed main() {
    TT {
        int n=read();
        for(int i=1;i<=n;i++)g[i].clear();
        for(int i=1;i<=n;i++) {
            a[i]=read();
            g[a[i]].push_back(i);
        }
        queue<int>q;
        for(int i=1;i<=n;i++)
            if(g[i].size()>0)q.push(i);
        int now=0;
        while(q.size()>1) {
            queue<int>tmp;
            vector<int>v;
            while(!q.empty()) {
                int x=q.front();
                q.pop();
                v.push_back(g[x][now]);
                if(now+1<g[x].size())tmp.push(x);
            }
            for(int i=1;i<v.size();i++)
                swap(a[v[i]],a[v[i-1]]);
            q=tmp;
            now++;
        }
        for(int i=1;i<=n;i++)cout<<a[i]<<' ';cout<<endl;
    }
    return 0;
}

//那怎么求一个数组的最少的交换次数呢？？