5.3.6 Cow Sorting （HDU 及 POJ）

Cow Sorting

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 67 Accepted Submission(s): 35

Problem Description

Sherlock's N (1 ≤ N ≤ 100,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 Sherlock's milking equipment, Sherlock 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 (necessarily adjacent) can be interchanged. Since grumpy cows are harder to move, it takes Sherlock a total of X + Y units of time to exchange two cows whose grumpiness levels are X and Y.

Please help Sherlock 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

Sample Output

Hint

Input Details Three cows are standing in line with respective grumpiness levels 2, 3, and 1. Output Details 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).

思路：RT，交换的两个值必须相邻，也就是这道题就是模拟插入排序的过程，那么我们用树状数组记录当前这个数之前的有多少个比它小的数，再做减法就可以了。

#include <cstdio>
#include <cstring>   
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;

typedef long long ll;
const int maxn=100200;
ll sum[maxn],cnt[maxn];
ll ccnt,ssum,ans,sum2;
int n,t;

void close()
{
	exit(0);
}

int lowbit(int k)
{
	return k & (-k);
}

void upd(ll *x,int k,int v)
{
	while (k<=n)
	{
		x[k]+=v;
		k+=lowbit(k);
	}
}

ll getsum(ll *x,int k)
{
	ll sum=0;
	while (k!=0)
	{
		sum+=x[k];
		k-=lowbit(k);
	}
	return sum;
}



void init()
{
    while(scanf("%d",&n)!=EOF)
	 {
		 ans=0;
		 sum2=0;
		 for (int i=1;i<=n;i++)
		 {
			 scanf("%d",&t);
			 ccnt=i-getsum(cnt,t-1)-1;
			 ssum=sum2-getsum(sum,t-1);
			 ans+=(ll)(ccnt*t+ssum);
			 upd(sum,t,t);
			 upd(cnt,t,1);
			 sum2+=t;
		 }
		 cout<<ans<<endl;
	 }
}


int main ()
{
	init();
	close();
}

POJ的：

Cow Sorting

Time Limit: 2000MS		Memory Limit: 65536K
Total Submissions: 5000		Accepted: 1837

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

Sample Output

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

思路：RT，题目上说交换两个数可以不相邻，那么这就是一个置换群了。给个网址：http://blog.csdn.net/qiqijianglu/article/details/7930544

上面讲的很详细了。

#include <cstdio>
#include <cstring>   
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
typedef long long ll;

const int maxn=100200;
int a[maxn],b[maxn];
ll sum,t1,t2,small,ans;
int l,n,minn;
bool f[maxn];

void close()
{
	exit(0);
}

void dfs(int k)
{
	if (not f[a[k]])
	{
		l++;
		sum+=a[k];
		f[a[k]]=true;
		minn=min(minn,a[k]);
		dfs(b[a[k]]);
	}
	else return;
}

void init()
{
   while(scanf("%d",&n)!=EOF)
   {
      ans=0;
		small=10000;
		small*=small;
		memset(f,false,sizeof(f));
		memset(a,0,sizeof(a));
		memset(b,0,sizeof(b));
	   for (int i=1;i<=n;i++)
		{
			scanf("%d",&a[i]);
			b[a[i]]=i;
			if (a[i]<small)
				small=a[i];
		}
		sort(a+1,a+n+1);
		for (int i=1;i<=n;i++)
			if (not f[a[i]])
			{
				l=0;
				sum=0;
				minn=a[i];
				dfs(i);
				if (l==1) continue;
				t1=(ll) ((l-2)*minn+sum);
				t2=(ll) (sum+minn+(l+1)*small);
				ans+=min(t1,t2);
			}
		cout<<ans<<endl;
	}
}


int main ()
{
	init();
	close();
	return 0;
}