s = {1 2 3 4 5 6}

t = {6 3 4 2 1 5}

1->6->5->1 那麼這些是一個輪換
2->3->4->2 這些是一個輪換

t = { {1 6 5},{ 2 3 4 } }，然後就衍生出了一些這樣的題目
1： nyoj900序列置換

AC程式碼：

``````#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <map>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <algorithm>
using namespace std;
const int N = 300;
const int inf = 0x3f3f3f3f;
typedef long long LL;
int next[N];
bool ok[N];
LL gcd(LL a,LL b)
{
return b==0?a:gcd(b,a%b);
}
int main()
{
int n;
while(~scanf("%d",&n))
{
for(int i=1;i<=n;i  )
{
scanf("%d",&next[i]);
}
LL ans = 1;
memset(ok,false,sizeof(ok));
for(int i=1;i<=n;i  )
{
if(ok[i]==false)
{
int tmp = i;
LL cnt = 1;
ok[i] = true;
while(next[tmp]!=i)
{
cnt  ;
tmp = next[tmp];
ok[tmp] = true;
}
LL css = gcd(ans,cnt);
ans = (ans*cnt)/css;
}
}
printf("%lld\n",ans);
}
return 0;
}
``````

2：poj3270 Cow Sorting

sum – min (len – 1) * min

sum (len – 2) * min

.考慮到另外一種情況，我們可以從別的迴圈裡面調一個數字，進入這個迴圈之中，使交換代價更小。例如初始狀態：1 8 9 7 6

sum min (len 1) * smallest

AC程式碼：

``````#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <map>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <algorithm>
using namespace std;
const int N = 10010;
const int inf = 0x3f3f3f3f;
int pss[N];
int a[N];
bool ok[10*N];
int next[10*N];
int main()
{
int n;
while(~scanf("%d",&n))
{
memset(ok,true,sizeof(ok));
int mi = inf,ma = -1;
for(int i=1;i<=n;i  ){
scanf("%d",&pss[i]);
a[i] = pss[i];
mi = min(mi,pss[i]);
ma = max(ma,pss[i]);
ok[ pss[i] ] = false;
}
sort(a 1,a 1 n);
for(int i=1;i<=n;i  )
{
next[ a[i] ] = pss[i];
}
int ans = 0;
for(int i=1;i<=ma;i  )
{
if(ok[next[i] ] == false)
{
int num = i, tmpmi = i;
int cnt = 1,count = i;
ok[num] = true;
while(next[num]!=i)
{
num = next[num];
cnt  ;
count =num;
ok[num] = true;
tmpmi = min(tmpmi,num);
}
ans =min(count (cnt-2)*tmpmi,count tmpmi (cnt 1)*mi);
}
}
printf("%d\n",ans);
}
return 0;
}