bzoj1697[Usaco2007 Feb] Cow Sorting牛排序

本文主要是介绍bzoj1697[Usaco2007 Feb] Cow Sorting牛排序，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：bzoj1697
题目大意：
N（1 <= N <= 10,000）头牛排队。农夫想把牛按脾气的大小排序（从小到大）。每一头牛的脾气都是一个在1到100，000之间的整数并且没有两头牛的脾气值相同。在排序过程中，可以交换任意两头牛的位置。需要X+Y秒来交换脾气值为X和Y的两头牛。求把所有牛排好序的最短时间。

题解：
置换
跟bzoj1119差不多

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
#define maxn 10010const LL inf=1e15;
struct node
{LL x;int id;
}a[maxn];
int b[maxn];LL c[maxn];bool vis[maxn];
bool cmp(node x,node y) {return x.x<y.x;}
LL mymin(LL x,LL y){return (x<y)?x:y;}
int main()
{//freopen("a.in","r",stdin);//freopen("a.out","w",stdout);int n,i,w;LL minf=inf,ans=0;scanf("%d",&n);for (i=1;i<=n;i++) {scanf("%lld",&a[i].x);a[i].id=i;(minf>a[i].x)?minf=a[i].x,w=i:w=w;vis[i]=false;}sort(a+1,a+1+n,cmp);for (i=1;i<=n;i++) b[a[i].id]=i,c[a[i].id]=a[i].x;for (i=1;i<=n;i++) if (!vis[i]){LL cnt,sum,mi;int ww,x=i;ww=x;sum=cnt=0;mi=c[x];while (!vis[x]){sum+=c[x];(mi>c[x])?mi=c[x],ww=x:w=w;vis[x]=true;cnt++;x=b[x];}if (ww==w) ans+=sum+mi*(cnt-2);else ans+=mymin(sum+mi*(cnt-2),sum+minf*(cnt+1)+mi);}printf("%lld\n",ans);return 0;
}

这篇关于bzoj1697[Usaco2007 Feb] Cow Sorting牛排序的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---