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

7

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

HINT

 

Source

题解:
黑书原题,排序的代价。
代码:
 #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 ;
}
04-13 13:27