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;

}