• 欢迎光临~

# 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 endl 'n'
const int M=2e5+5;

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 {
for(int i=1;i<=n;i++)g[i].clear();
for(int i=1;i<=n;i++) {
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;
}
``````

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