【BZOJ 1697】1697: [Usaco2007 Feb]Cow Sorting牛排序

时间：2022-09-23 17:15:28

1697: [Usaco2007 Feb]Cow Sorting牛排序

Description

农夫JOHN准备把他的 N（1 <= N <= 10,000）头牛排队以便于行动。因为脾气大的牛有可能会捣乱，JOHN想把牛按脾气的大小排序。每一头牛的脾气都是一个在1到100，000之间的整数并且没有两头牛的脾气值相同。在排序过程中，JOHN 可以交换任意两头牛的位置。因为脾气大的牛不好移动，JOHN需要X+Y秒来交换脾气值为X和Y的两头牛。 请帮JOHN计算把所有牛排好序的最短时间。

Input

第1行： 一个数， N。

第2~N+1行： 每行一个数，第i+1行是第i头牛的脾气值。

Output

第1行： 一个数，把所有牛排好序的最短时间。

Sample Input

3
2
3
1

输入解释：

队列里有三头牛，脾气分别为 2，3， 1。

Sample Output

7

输出解释：
2 3 1 : 初始序列
2 1 3 : 交换脾气为3和1的牛(时间=1+3=4).
1 2 3 : 交换脾气为1和2的牛(时间=2+1=3).

【分析】

　　又傻了，想了很久，只想到第一种情况，以为这就是最优的。

　　其实就是一种置换，要把它换回原位。

　　先分解成互不相交的循环。

　　对于同一个循环里面的元素，最好就是每次都用最小的一个和别人交换，代价是sum + (len – 2) * min

　　其实的话，还有一种，就是先把一个全局最小的移过来，换完了之后再移回去，代价是sum + min + (len + 1) * smallest

　　取两种方法中最小的一个。

　　至于为什么只有这两种，我也不太清楚，但想想好像跨组的情况除了第二种也没什么可以更优的了。

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 using namespace std;

 #define Maxn 10010

 #define INF 0xfffffff

 struct node

 {

     int a,b,id;

 }t[Maxn];

 bool vis[Maxn];

 int mymin(int x,int y) {return x<y?x:y;}

 int mymax(int x,int y) {return x>y?x:y;}

 bool cmp(node x,node y) {return x.a<y.a;}

 bool cmp2(node x,node y) {return x.id<y.id;}

 int main()

 {

     int n,ans=,mnn=INF,mx=;

     scanf("%d",&n);

     for(int i=;i<=n;i++)

     {

         // scanf("%d",&a[i]);

         scanf("%d",&t[i].a);

         t[i].id=i;

         mnn=mymin(mnn,t[i].a);

         mx=mymax(mx,t[i].a);

     }

     sort(t+,t++n,cmp);

     for(int i=;i<=n;i++) t[i].b=i;

     sort(t+,t++n,cmp2);

     memset(vis,,sizeof(vis));

     for(int i=;i<=n;i++) if(vis[i]==)

     {

         int mn=INF,x=i,h=,cnt=;

         while(vis[x]==)

         {

             cnt++;

             vis[x]=;

             mn=mymin(mn,t[x].a);

             h+=t[x].a;

             x=t[x].b;

         }

         ans+=mymin((cnt-)*mn+h,h+mn+(cnt+)*mnn);

     }

     printf("%d\n",ans);

     return ;

 }

2017-01-12 19:53:21

相关文章