终于把这个很久以前拖下来的问题解决了

回忆一下，最少相邻交换次数等于逆序对数

这里求的是最少交换代价（非相邻元素也可以交换）；

先考虑最少交换次数这个问题

首先把现在数列看成原数列{1,2,3……n}的一个置换

根据置换的理论，每一个置换都能拆成唯一的互不相交的循环

显然最小交换次数是在每个循环内部交换达成的

在一个包含元素数位x的循环内，交换成原数列的最小次数显然为x-1

最小交换次数就很明显了

而这里求的是最小交换代价，显然循环内部每个元素都要交换一次（除了只含一个元素的循环）

首先想到的是用每个循环内最小元素使循环内其他元素归位

注意还有一种情况，我们可以把整个序列里的最小元素a和这个循环里最小的b交换，然后用元素a与循环内其他元素交换，最后再把

a交换出循环（a和b交换）

最小代价就是取这两种方法较小的那一个

1 var a,b:array[0..10010] of longint; 2     f:array[0..100010] of longint; 3     v:array[0..100010] of boolean; 4     t,x,max,i,n,s,ans:longint; 5  6 function min(a,b:longint):longint; 7   begin 8     if a>b then exit(b) else exit(a); 9   end;10 11 procedure dfs(x:longint);   //找循环12   begin13     v[x]:=true;14     ans:=ans+a[x];15     inc(s);16     if not v[b[x]] then dfs(b[x]);17   end;18 19 begin20   readln(n);21   for i:=1 to n do22   begin23     readln(x);24     if x>max then max:=x;25     f[x]:=i;26   end;27   for i:=1 to max do  28     if f[i]>0 then29     begin30       inc(t);31       b[f[i]]:=t;32       a[t]:=i;33     end;34 35   for i:=1 to n do36     if not v[i] then37     begin38       s:=0;39       dfs(i);40       ans:=ans+min((s-2)*a[i],(s+1)*a[1]+a[i]);41     end;42 43   writeln(ans);44 end.