PKU 1674 Sorting by Swapping
http://poj.org/problem?id=1674
n個の数字1〜nを含む数列がある。これをスワップしてソートするとき、最小のスワップ回数はいくらかというような問題。
in[位置]=値、とpos[値]=位置という二つの配列を用意して小さい方から順番にスワップしていった。多少混乱した。
int in[10000]; int pos[10000]; main(){ int t; cin>>t; while(t--){ int n; cin>>n; rep(i,n){ cin>>in[i]; in[i]--; pos[in[i]]=i; } int ans=0; rep(i,n){ if(in[i]==i)continue; int t=in[i]; int p=pos[i]; ++ans; swap(in[i],in[p]); pos[i]=i; pos[t]=p; } cout<<ans<<endl; } }