Submit: 653 Solved: 378
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。
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).
输出解释：
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 #include<algorithm> 3 #include<iostream> 4 #include<cstring> 5 #include<cstdio> 6 #include<cmath> 7 #include<vector> 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 ",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 ",ans); 54 return 0; 55 }