BZOJ1697 [Usaco2007 Feb] Cow Sorting牛排序

農夫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

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).

題解

置換群2333

來自novosbirsk的題解

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之中小的那個數字。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define ll long long
#define inf 1000000000
using namespace std;
inline ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,gmn,cnt,ans;
int v[10005],id[10005],disc[10005];
int mn[10005],sum[10005],len[10005];
bool vis[10005];
int find(int x)
{
	int l=1,r=n;
	while(l<=r)
	{
		int mid=(l+r)>>1;
		if(disc[mid]>x)r=mid-1;
		else if(disc[mid]==x)return mid;
		else l=mid+1;
	}
}
void solve(int x)
{
	vis[x]=1;cnt++;
	len[cnt]=1;sum[cnt]+=v[x];mn[cnt]=min(mn[cnt],v[x]);
	int now=x;
	while(v[id[now]]!=v[x])
	{
		now=id[now];vis[now]=1;
		len[cnt]++;sum[cnt]+=v[now];mn[cnt]=min(mn[cnt],v[now]);
	}
}
int main()
{
	memset(mn,127/3,sizeof(mn));gmn=inf;
	n=read();
	for(int i=1;i<=n;i++)
		v[i]=read(),disc[i]=v[i],gmn=min(gmn,v[i]);
	sort(disc+1,disc+n+1);
	for(int i=1;i<=n;i++)
		id[i]=find(v[i]);
	for(int i=1;i<=n;i++)
		if(!vis[i]&&i!=id[i])solve(i);
	for(int i=1;i<=cnt;i++)
	{
		int t1=(len[i]-2)*mn[i];
		int t2=mn[i]+(len[i]+1)*gmn;
		ans+=sum[i]+min(t1,t2);
	}
	printf("%d",ans);
	return 0;
}