题意：要求用两两交换的方式给一个数列排序，交换f[i]和f[j]的代价为f[i]+f[j]，求最小代价。
分析：具体方法就是在数列中找置换环，每个环有两种处理方式，一种是用最小的元素将环里所有元素归位，另一种是用全数列最小元素与环内最小元素交换，并在环内用这个全数列最小元素将环里所有元素归位，再与原环内最小元素交换回来。
View Code #include#include #include #include #include using namespace std;#define maxn 10005#define maxg 100005struct Elem{ int v, index;}elem[maxn];int n;int f[maxn];bool vis[maxn];int pos[maxg];bool operator < (const Elem &a, const Elem &b){ return a.v < b.v;}void input(){ scanf("%d", &n); for (int i = 0; i < n; i++) { scanf("%d", &elem[i].v); elem[i].index = i; f[i] = elem[i].v; }}int work(){ for (int i = 0; i < n; i++) pos[elem[i].v] = i; int mini = 0; for (int i = 0; i < n; i++) if (f[i] < f[mini]) mini = i; int ret = 0; for (int i = 0; i < n; i++) if (!vis[i]) { int sum = 0, temp = i, x = f[i], num = 0; while (!vis[temp]) { vis[temp] = true; sum += f[temp]; x = min(x, f[temp]); temp = pos[f[temp]]; num++; } ret += min((num - 1) * x + sum - x, (num - 1) * f[mini] + sum - x + (x + f[mini]) * 2); } return ret;}int main(){ //freopen("t.txt", "r", stdin); memset(vis, 0, sizeof(vis)); input(); sort(elem, elem + n); printf("%d\n", work()); return 0;}