Description
农夫JOHN准备把他的 N（1 <= N <= 10,000）头牛排队以便于行动。因为脾气大的牛有可能会捣乱，JOHN想把牛按脾气的大小排序。每一头牛的脾气都是一个在1到100，000之间的整数并且没有两头牛的脾气值相同。在排序过程中，JOHN 可以交换任意两头牛的位置。因为脾气大的牛不好移动，JOHN需要X+Y秒来交换脾气值为X和Y的两头牛。 请帮JOHN计算把所有牛排好序的最短时间。
Input
第1行： 一个数， N。
第2~N+1行： 每行一个数，第i+1行是第i头牛的脾气值。
Output
第1行： 一个数，把所有牛排好序的最短时间。
Sample Input
3 2 3 1 输入解释： 队列里有三头牛，脾气分别为 2，3， 1。
Sample Output
7 输出解释： 2 3 1 : 初始序列 2 1 3 : 交换脾气为3和1的牛(时间=1+3=4). 1 2 3 : 交换脾气为1和2的牛(时间=2+1=3).
HINT
Source
数学问题 置换群
“初始状态某位置的牛”和“排序后状态的对应位置的牛”显然是在同一个置换里的
找出置换群，对于每个环，最优换法肯定是用代价最小的那个点把其他点换到正确位置上。
这样做的代价是sum（环内脾气总和）-mini（最小的脾气）+(num(环内结点数量)-1)*mini
但是还有另一种情况，就是从置换群外面找一头脾气更小的牛进来，把所有点归位，再把它换出去
这样做的代价是sum+mini+num*MIN(所有牛中脾气最小的)
两者取最小即可
1 /*by SilverN*/ 2 #include3 #include 4 #include 5 #include 6 #include 7 #include 8 using namespace std; 9 const int mxn=100010;10 int read(){11 int x=0,f=1;char ch=getchar();12 while(ch<'0' || ch>'9'){ if(ch=='-')f=-1;ch=getchar();}13 while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}14 return x*f;15 }16 int n,mini=1e9;17 int a[mxn],b[mxn];18 int vl[mxn],id[mxn];19 //20 int sum[mxn],mi[mxn],sz[mxn],cnt;21 bool vis[mxn];22 void solve(int x){23 sum[++cnt]=a[x];mi[cnt]=a[x];sz[cnt]=1;24 vis[x]=1;int t=id[x];25 while(!vis[t]){26 vis[t]=1;27 sum[cnt]+=a[t];28 mi[cnt]=min(mi[cnt],a[t]);29 sz[cnt]++;30 t=id[t];31 }32 return;33 }34 int main(){35 int i,j;36 n=read();37 for(i=1;i<=n;i++)a[i]=read(),b[i]=a[i],mini=min(mini,a[i]);38 sort(b+1,b+n+1);39 for(i=1;i<=n;i++){40 vl[b[i]]=i;41 }42 for(i=1;i<=n;i++){43 id[i]=vl[a[i]]; 44 }45 for(i=1;i<=n;i++){46 if(!vis[i])solve(i);47 }48 int ans=0;49 for(i=1;i<=cnt;i++){50 // printf("sum:%d mi:%d sz:%d\n",sum[i],mi[i],sz[i]);51 ans+=min(sum[i]-mi[i]+mi[i]*(sz[i]-1),sum[i]+mi[i]+mini*(sz[i]+1));52 }53 printf("%d\n",ans);54 return 0;55 }