对于组合数学是一点也不了解
重要一点 要知道一个循环里最少的交换次数是m-1次 、
1 #include <iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<stdlib.h> 6 using namespace std; 7 #define N 10010 8 #define INF 0xfffffff 9 int a[N],b[N],po[N*10],vis[N*10]; 10 int main() 11 { 12 int i,n; 13 while(scanf("%d",&n)!=EOF) 14 { 15 memset(vis,0,sizeof(vis)); 16 for(i = 1 ; i <= n ;i++) 17 { 18 scanf("%d",&a[i]); 19 b[i] = a[i]; 20 } 21 sort(b+1,b+n+1); 22 for(i = 1 ; i <= n ; i++) 23 po[b[i]] = i; 24 int ans=0; 25 for(i = 1 ; i <= n ; i++) 26 { 27 if(!vis[a[i]]) 28 { 29 int sum = a[i],minz = INF ,o = a[i],t=0; 30 while(1) 31 { 32 vis[o] = 1; 33 t++; 34 minz = min(minz,o); 35 int k = po[o]; 36 o = a[k]; 37 if(vis[o]) 38 break; 39 sum+=o; 40 } 41 ans +=min(sum-minz+minz*(t-1),sum+minz+b[1]*(t+1)); 42 } 43 } 44 printf("%d ",ans); 45 } 46 return 0; 47 }