大致题意：给出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; }