题目：有一串数字，要将它排列成升序，每次可以交换两个数，交换一次的代价为两数之和，求代价最小是多少。
思路：置换。对于每个循环，要么是用当前循环内最小的数mi去和其他数交换，要么是用全局最小值MIN和mi交换，然后用MIN去和循环内其他的数进行交换，然后MIN再和mi去交换。
假设循环长度为cnt，循环内所有数的和为sum，那么答案就是sum+min((cnt-2)*mi,mi+(cnt+1)*MIN)。
代码：
#pragma comment(linker, "/STACK:1024000000,1024000000") #include<iostream> #include<algorithm> #include<ctime> #include<cstdio> #include<cmath> #include<cstring> #include<string> #include<vector> #include<map> #include<set> #include<queue> #include<stack> #include<list> #include<numeric> using namespace std; #define LL long long #define ULL unsigned long long #define INF 0x3f3f3f3f3f3f3f3f #define mm(a,b) memset(a,b,sizeof(a)) #define PP puts("*********************"); template<class T> T f_abs(T a){ return a > 0 ? a : -a; } template<class T> T gcd(T a, T b){ return b ? gcd(b, a%b) : a; } template<class T> T lcm(T a,T b){return a/gcd(a,b)*b;} // 0x3f3f3f3f3f3f3f3f const int maxn=1e4+50; int arr[maxn],Hash[maxn],vis[maxn]; int main(){ int n,MIN; while(~scanf("%d",&n)){ MIN=1000000; for(int i=1;i<=n;i++){ scanf("%d",&arr[i]); Hash[i]=arr[i]; MIN=min(MIN,arr[i]); } sort(Hash+1,Hash+n+1); for(int i=1;i<=n;i++) arr[i]=lower_bound(Hash+1,Hash+n+1,arr[i])-Hash; mm(vis,0); int ans=0; for(int i=1;i<=n;i++){ if(vis[i]) continue; int cnt=0,pos=i,mi=Hash[i]; while(vis[pos]==0){ ans+=Hash[pos]; mi=min(mi,Hash[pos]); vis[pos]=1; cnt++; pos=arr[pos]; } // printf("%d %d %d %d\n",MIN,mi,cnt,ans); ans=ans+min((cnt-2)*mi,mi+(cnt+1)*MIN); } printf("%d\n",ans); } return 0; }