【算法】数学置换
【题意】给定n个数，要求通过若干次交换两个数的操作得到排序后的状态，每次交换代价为两数之和，求最小代价。
【题解】
考虑置换的定义：置换就是把n个数做一个全排列。
从原数组到排序数组的映射就是经典的置换，这样的置换一定能分解成循环的乘积。
为什么任意置换都可以这样分解：原数组的每个数要交换到排序位置（有后继），每个数的原位置会有数字来替代（有前驱），故一定构成若干循环节。
循环节内要完成置换，需要按顺序依次替换位置进行len-1次对换（len为循环节长度）。
对于每一循环节内部，最高效的方法就是拿最小的数num来进行len-1次交换，代价为sum-num+(len-1)*num即sum+(len-2)*num。
还有一种方法，是从其它循环节拿一个数字（显然拿全局最小）替换当前循环节最小数完成len-1次对换后再换回去，即sum+(len+1)*min+num。
找到每个循环节然后将两个代价中较小者计入答案。
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=;
int a[maxn],n,ms,ans=;
bool vis[maxn];
struct cyc{int num,id;}b[maxn]; bool cmp(cyc a,cyc b){return a.num<b.num;}
int main(){
scanf("%d",&n);
ms=0x3f3f3f3f;
for(int i=;i<=n;i++){
scanf("%d",&b[i].num);
b[i].id=i;
ms=min(ms,b[i].num);
}
sort(b+,b+n+,cmp);
for(int i=;i<=n;i++)a[b[i].id]=i;
for(int i=;i<=n;i++)if(!vis[i]){
int sum=,num=0x3f3f3f3f,x=i,len=;
while(!vis[x]){
num=min(num,b[x].num);
sum+=b[x].num;
vis[x]=;
x=a[x];
len++;
}
ans+=min(sum+(len-)*num,sum+num+(len+)*ms);
}
printf("%d",ans);
return ;
}