3270 Cow Sorting //利用置换排序

Cow Sorting

Time Limit: 2000MS	Memory Limit: 65536K
Total Submissions: 3610	Accepted: 1196

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

3
2
3
1      

Sample Output

7      

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 将原序列按照升序排序，可以交换任意两个元素，但是每次交换所付出的代价是两个元素的和，使和最小 利用置换解这道题

/*

感谢这位作者：http://hi.baidu.com/novosbirsk/blog/item/58c5fcfa46911e9159ee90b9.html

1.找出初始状态和目标状态。明显，目标状态就是排序后的状态。

2.画出置换群，在里面找循环。例如，数字是8 4 5 3 2 7

明显，目标状态是2 3 4 5 7 8，能写为两个循环：

(8 2 7)(4 3 5)。

3.观察其中一个循环，明显地，要使交换代价最小，应该用循环里面最小的数字2，去与另外的两个数字，7与8交换。这样交换的代价是：

sum - min + (len - 1) * min

化简后为：

sum + (len - 2) * min

其中，sum为这个循环所有数字的和，len为长度，min为这个环里面最小的数字。

4.考虑到另外一种情况，我们可以从别的循环里面调一个数字，进入这个循环之中，使交换代价更小。例如初始状态：

1 8 9 7 6

可分解为两个循环：

(1)(8 6 9 7)，明显，第二个循环为(8 6 9 7)，最小的数字为6。我们可以抽调整个数列最小的数字1进入这个循环。使第二个循环变为：(8 1 9 7)。让这个1完成任务后，再和6交换，让6重新回到循环之后。这样做的代价明显是：

sum + min + (len + 1) * smallest

其中，sum为这个循环所有数字的和，len为长度，min为这个环里面最小的数字，smallest是整个数列最小的数字。

5.因此，对一个循环的排序，其代价是sum - min + (len - 1) * min和sum + min + (len + 1) * smallest之中小的那个数字。

6.我们在计算循环的时候，不需要记录这个循环的所有元素，只需要记录这个循环的最小的数及其和。

7.在储存数目的时候，我们可以使用一个hash结构，将元素及其位置对应起来，以达到知道元素，可以快速反查元素位置的目的。这样就不必要一个个去搜索。

*/

#include<cstdio>

#include<algorithm>

#include<cstring>

using namespace std;

int cow[10010],acow[10010];

int hash[100010];

bool vis[10010];

int main()

{

int n;

scanf("%d",&n);

int rmin=1<<25;

memset(vis,false,sizeof(vis));

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

{

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

acow[i]=cow[i];

if(rmin>cow[i]) rmin=cow[i];//rmin，全局最小值

hash[cow[i]]=i; /* 读取数据，并建立简单的hash结构，用于知道元素反查其位置*/

}

sort(acow,acow+n);/* 排序，目标状态存储在acows之中 */

int len,semin,i;

int length=n;

int ans=0;

while(length)/* 寻找置换群之中的循环 */

{

i=len=0;//起始点和长度置0

int sum=0;

semin=1<<25;

while(vis[i]) i++;//找到起始点

int begin=i;//记录起始点

while(1)

{

len++;

vis[i]=1;

if(cow[i]<semin) semin=cow[i];

sum+=cow[i];

i=hash[acow[i]];//参照目标状态找到循环

/*1 2 3 4 5

3 4 2 1 5

(1 3 2 4) (5)

*/

if(i==begin) break;

}

length-=len;

if(len==1) continue;//只有一个元素的循环不需要变动

int v1=(len-2)*semin;

int v2=semin+(len+1)*rmin;

ans+=(v1<v2)?v1:v2;

ans+=sum;

}

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

return 0;

}