BZOJ1697: [Usaco2007 Feb]Cow Sorting牛排序

1697: [Usaco2007 Feb]Cow Sorting牛排序

Time Limit: 5 Sec Memory Limit: 64 MB
Submit: 387 Solved: 215
[Submit][Status]

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

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

HINT

Source

Gold

题解：

黑书原题，排序的代价。

代码：

 #include<cstdio>

 #include<cstdlib>

 #include<cmath>

 #include<cstring>

 #include<algorithm>

 #include<iostream>

 #include<vector>

 #include<map>

 #include<set>

 #include<queue>

 #include<string>

 #define inf 1000000000

 #define maxn 15000

 #define maxm 500+100

 #define eps 1e-10

 #define ll long long

 #define pa pair<int,int>

 #define for0(i,n) for(int i=0;i<=(n);i++)

 #define for1(i,n) for(int i=1;i<=(n);i++)

 #define for2(i,x,y) for(int i=(x);i<=(y);i++)

 using namespace std;

 inline int read()

 {

     int x=,f=;char ch=getchar();

     while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

     while(ch>=''&&ch<=''){x=*x+ch-'';ch=getchar();}

     return x*f;

 }

 ll n,mi,cs=,a[maxn],b[maxn],c[maxn];

 bool check[maxn];

 inline bool cmp(int x,int y)

 {

     return a[x]<a[y];

 }

 int main()

 {

     freopen("input.txt","r",stdin);

     freopen("output.txt","w",stdout);

     n=read();

     for1(i,n)a[i]=read(),b[i]=i;

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

     for1(i,n)c[b[i]]=i;

     ll ans=;

     mi=a[b[]];

     for1(i,n)

      if(!check[i])

       {

           ll j=i,len=,tmp=inf,sum=;

           while(!check[j])

           {

            check[j]=;

            tmp=min(tmp,a[j]);

            sum+=a[j];

            len++;

            j=c[j];

           }

         ans+=sum+min((len-)*tmp,mi*(len+)+tmp);

       }

     cout<<ans<<endl;

     return ;

 }