本文主要是介绍poj3270 Cow Sorting 置换群，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：有一个序列，你需要将通过交换使得序列最后单调增。每次交换的代价为交换的两个数的和，求将序列变成单调增地最小代价
和。
思路：如果有一个序列：8 4 5 3 2 7 ，那么最终的序列为：2 3 4 5 7 8 。如果视作是一个置换群的作用，那么可以写出循环之积：
（8 2 7）（4 3 5）。对于每个循环，每个数都至少被交换一次，所以我们应该用循环中的最小值和每个数交换，设循环数的最小值
为x,循环内所有数的和为sum，循环内有cnt个数，那么代价和为sum + (cnt - 2)*x 。不过我们还可以从n个数中取最小值不妨设为min
可以让min先和x的位置交换，然后用min与循环内的数交换完，此时min的位置必然是x的最终位置，再将x和min的位置交换，代价和
为sum+(cnt + 1)*min+x; 对于每个循环的代价和一定是这两种情况的最小值，最后用ans累加每个循环的最小代价和即可。详见代
码：
// file name: poj3270.cpp //
// author: kereo //
// create time: 2014年09月01日 星期一 15时54分25秒 //
//***********************************//
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<set>
#include<map>
#include<vector>
#include<stack>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long ll;
const int MAXN=10000+100;
const int inf=0x3fffffff;
#define L(x) (x<<1)
#define R(x) (x<<1|1)
int n;
int a[MAXN],vis[MAXN],hash[10*MAXN]; //值映射地址
int main()
{while(~scanf("%d",&n)){memset(vis,0,sizeof(vis));memset(hash,0,sizeof(hash));int Min=inf;for(int i=1;i<=n;i++){scanf("%d",&a[i]);hash[a[i]]=i; Min=min(Min,a[i]);}sort(a+1,a+n+1);ll ans=0;for(int i=1;i<=n;i++) if(!vis[i]){ll sum=0;int res=inf,x=i,cnt=0;while(!vis[x]){cnt++;sum+=a[x]; res=min(res,a[x]);vis[x]=1; x=hash[a[x]];}ans+=sum+min((ll)(cnt-2)*(ll)res,(ll)(cnt+1)*(ll)Min+(ll)res);}cout<<ans<<endl;}return 0;
}这篇关于poj3270 Cow Sorting 置换群的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
