poj3270 Cow Sorting 置换环+贪心

177 阅读 0 评论 117 点赞

我是靠谱客的博主烂漫电脑，这篇文章主要介绍poj3270 Cow Sorting 置换环+贪心，现在分享给大家，希望可以做个参考。

Cow Sorting

Time Limit: 2000MS		Memory Limit: 65536K
Total Submissions: 7455		Accepted: 2926

Description

Farmer John's N (1 ≤ N ≤ 10,000) cows are lined up to be milked in the evening. Each cow has a unique "grumpiness" level in the range 1...100,000. Since grumpy cows are more likely to damage FJ's milking equipment, FJ would like to reorder the cows in line so they are lined up in increasing order of grumpiness. During this process, the places of any two cows (not necessarily adjacent) can be interchanged. Since grumpy cows are harder to move, it takes FJ a total of X+Y units of time to exchange two cows whose grumpiness levels are X and Y.

Please help FJ calculate the minimal time required to reorder the cows.

Input

Line 1: A single integer: N.
Lines 2.. N+1: Each line contains a single integer: line i+1 describes the grumpiness of cow i.

Output

Line 1: A single line with the minimal time required to reorder the cows in increasing order of grumpiness.

Sample Input

Sample Output

Hint

2 3 1 : Initial order.
2 1 3 : After interchanging cows with grumpiness 3 and 1 (time=1+3=4).
1 2 3 : After interchanging cows with grumpiness 1 and 2 (time=2+1=3).

Source

USACO 2007 February Gold

题意：给定一个序列，交换两个数的操作消耗为两个数之和，求将其变换到升序序列的消耗。

题解：贪心思想，首先我们要使得消耗最少，移动的次数要少。那么，可以先想到策略一，在含有m个数的置换环内操作，每次拿环中最小的数字与其他数字交换，共交换m-1次。有公式ans=x[1]+L+x[2]+L+...+x[m-1]+L，整理得ans=sum+(m-2)*L(L为置换环中最小数)。但这不一定最优还有一种策略二：将数组中最小的一个数作为中介，先把他和置换环中最小数交换，将先他带入置换环，然后进行m-1次操作，最后再将该数换出去，公式：ans=min+L+x[1]+min+x[2]+min+...+x[m-1]+min+min+L，整理得ans=sum+L+2*min。对于每一个置换环，取上述两个策略中最小求和即可。

代码：

#include<set>
#include<map>
#include<stack>
#include<queue>
#include<vector>
#include<string>
#include<bitset>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<iomanip>
#include<iostream>
#define debug cout<<"aaa"<<endl
#define mem(a,b) memset(a,b,sizeof(a))
#define LL long long
#define lson l,mid,root<<1
#define rson mid+1,r,root<<1|1
#define MIN_INT (-2147483647-1)
#define MAX_INT 2147483647
#define MAX_LL 9223372036854775807i64
#define MIN_LL (-9223372036854775807i64-1)
using namespace std;
const int N = 10000 + 5;
const int mod = 1000000000 + 7;
struct node{
int num,id;
}a[N];
bool vis[N];
bool cmp(node a,node b){
return a.num<b.num;
}
int main(){
int n,minn=MAX_INT,sum,m,num,cnt;
LL ans=0;
mem(vis,0);
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i].num);
minn=min(minn,a[i].num);
a[i].id=i;
}
sort(a+1,a+n+1,cmp);
for(int i=1;i<=n;i++){
if(!vis[i]){
cnt=1;
sum=m=a[i].num;
vis[i]=1;num=a[i].id;
while(num!=i){
cnt++;vis[num]=1;
sum+=a[num].num;
m=min(m,a[num].num);
num=a[num].id;
}
ans+=min(sum+(cnt-2)*m,sum+m+(cnt+1)*minn);
}
}
printf("%lldn",ans);
return 0;
}