大致題意：給出n個整數，要將它們轉化成遞增序列，每交換其中兩個數的代價是這兩個數之和。問排序成功後的最小代價。
該題考察的是置換群知識。在黑書p247上有詳細的講解。總結下置換群，方便復習。
群：給定一個集合G={a,b,c...}和集合G上的二元運算 ·，如果滿足封閉性，結合律，存在單位元和逆元，則成集合G在運算'·'之下是一個群。
置換：n個元素1,2,....,n之間的置換可表示為
1 2 3 ... n
a1 a2 a3 ... an
表示1被1到n中的某個數a1代替，2被1到n中的某個數a2代替，直到n被1到n中的某個數an代替，且a1,a2....an互不相同。
置換群：是若干置換的集合。運算是置換的連接。
a1 a2 a3 .... an
循環：記(a1,a2...an) = a2 a3 a4 .... a1 稱為n階循環。每個置換都可以寫成若干個循環的乘積。
例如置換1 2 3 4 5 6 = （1 3 6 ）（2 5 ）（4）
3 5 6 4 2 1
置換的循環節數就是上述循環的個數，例如上面循環節數就是3。
回到本題。例如有一個序列： 1 8 9 7 6
要將 1 8 9 7 6 變成有序序列 1 6 7 8 9，可以看做要完成一個置換
1 8 9 7 6
1 6 7 8 9
因為每個置換都可看做若干輪換(循環)的乘積，那麼上述置換可表示成兩個循環（1）（6,7,8,9）的乘積。而我們的目的是變成循環(1)(6)(7)(8)(9),所以每次對換一定是在同一個循環中的兩個元素之間進行。
然後對於一個循環i,設它的長度是ki,那麼它至少要交換ki-1次，即每次讓一個元素到達目標位置。既然交換次數一定，那麼要使交換的代價最小，就是每次都拿循環裡最小的元素ti與其他元素交換。根據這些知識，我們得知解決原題，有兩種方案：
1.對於每個循環，都那該循環裡最小的元素ti與其他元素交換，那麼共花費 sumi + (ki-2)*ti,（sumi是該循環個元素之和）
2.讓ti先和n個元素中最小的元素m交換，讓m進入該循環，並和剩下的ki-1個元素依次交換把他們送入目標位置，然後再讓m和ti交換，ti退出該循環。這樣共花費 sumi + ti + (ki+1)*m
綜上：所有循環都交換完所需的最小花費cost = sum + ∑min{ (ki-2)*ti , ti + (ki+1)*m };
對於求各個循環，拿兩個數組來回記錄一下就可以了。由上式可以看出我們只需記錄每個循環的ki（長度）和ti（最小元素）。
#include#include #include #include using namespace std; const int INF = 0x3f3f3f3f; struct node { int num; int Min; }ans[10010]; //記錄每個循環的長度和最小元素 int main() { int n,a[10010],b[1000010]; int vis[1000010]; int cnt,Min; int i,t; int ans_num; int sum; int Minn; while(~scanf(%d,&n)) { sum = 0; Minn = INF; for(i = 1; i <= n; i++) { scanf(%d,&a[i]); sum += a[i]; b[a[i]] = i; Minn = min(Minn,a[i]); //n個數中的最小數 } sort(a+1,a+1+n); memset(vis,0,sizeof(vis)); ans_num = 0; while(1) { //每次找出一個未被訪問的數，從這個數開始找其所在的循環 for(i = 1; i <= n; i++) if(!vis[a[i]]) break; if(i > n) break; cnt = 0; //該循環的元素個數 Min = INF;//該循環中最小的元素 t = a[i]; while(1) { vis[t] = 1; Min = min(Min,t); cnt++; if(!vis[a[b[t]]]) t = a[b[t]]; else break; } ans[++ans_num] = (struct node){cnt,Min}; } for(int i =1; i <= ans_num; i++) { int num = ans[i].num; int Min = ans[i].Min; sum += min((num-2)*Min, Min + (num+1)*Minn); } printf(%d ,sum); } return 0; }
