置换群好题一枚
2种决策:
取循环内最小的数参与循环的置换,循环内有n个元素,进行n-1次;
取循环外最小的数进来参与循环的置换,再交换回去
#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <map> #include <set> #include <algorithm> #include <vector> #include <string> using namespace std; #define N 10500 #define ll long long int a[N],b[N],c[N*10],vis[N]; int n; int main () { while(scanf("%d",&n)!=EOF) { for(int i=1;i<=n;++i) { scanf("%d",&a[i]); b[i]=a[i]; } sort(b+1,b+1+n); for(int i=1;i<=n;++i) c[b[i]]=i; ll m=b[1],sum,mi,ti,ans=0; memset(vis,0,sizeof(vis)); for(int i=1;i<=n;++i) if(!vis[i]) { int j=i; sum=a[j]; ti=1; mi=a[j]; vis[j]=1; while(!vis[c[a[j]]]) { j=c[a[j]]; vis[j]=1; sum+=a[j]; mi=min(mi,(ll)a[j]); ti++; } ans+=sum+min((ti-2)*mi,(ti+1)*m+mi); } cout<<ans<<endl; } return 0; }