并不应该叫置换群……只是用到了置换而已，并没有群。
题解看这个吧，我就不写了：http://www.cnblogs.com/kuangbin/archive/2012/09/03/2669013.html
证明的话可以自己手撸几组数据模拟一下，比较容易。
复杂度O（n）。
算是个经典题吧？
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
#define INF 2147483647
vector<int>vs[10010];
struct data{
int p,v;
}t[10010];
bool cmp(const data &a,const data &b){
return a.v<b.v;
}
int n,e,ma[10010],minn=INF,ans,t1,t2,minx;
bool vis[10010];
int a[10010];
void dfs(int U){
vis[U]=1;
minx=min(minx,ma[U]);
if(!vis[a[U]]){
dfs(a[U]);
}
t1+=(minx+ma[U]);
t2+=(minn+ma[U]);
}
int main(){
// freopen("poj3270.in","r",stdin);
scanf("%d",&n);
for(int i=1;i<=n;++i){
scanf("%d",&t[i].v);
t[i].p=i;
minn=min(t[i].v,minn);
}
sort(t+1,t+n+1,cmp);
for(int i=1;i<=n;++i){
if(t[i].v!=t[i-1].v){
++e;
}
a[e]=t[i].p;
ma[e]=t[i].v;
}
for(int i=1;i<=n;++i){
if(!vis[a[i]]){
t1=t2=0;
minx=INF;
dfs(a[i]);
t1-=(minx+minx);
t2+=(minx+minn);
ans+=min(t1,t2);
}
}
printf("%d\n",ans);
return 0;
}