首页 > ACM题库 > HDU-杭电 > HDU 2838-Cow Sorting-线段树-[解题报告]HOJ
2014
02-17

HDU 2838-Cow Sorting-线段树-[解题报告]HOJ

Cow Sorting

问题描述 :

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.

输入:

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.

输出:

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.

样例输入:

3
2
3
1

样例输出:

7

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

题意:给你N个排列不规则的数,任务是把它从小到大排好,每次只能交换相邻两个数,交换一次的代价为两数之和,求最小代价

#include<iostream>
using namespace std;
#define N 100001
int n;
struct node
{
	int index;
	__int64 sum;
}c[N];
int lowbit(int x)
{
	return x&(-x);
}
void update(int x,int k,int s)
{
	while(x<=n)
	{
		c[x].index+=k;
		c[x].sum+=s;
		x+=lowbit(x);
	}
}
int getsum_index(int x)
{
	int ans=0;
	while(x>0)
	{
		ans+=c[x].index;
		x-=lowbit(x);
	}
	return ans;
}
__int64 getsum_sum(int x)
{
	__int64 ans=0;
	while(x>0)
	{
		ans+=c[x].sum;
		x-=lowbit(x);
	}
	return ans;
}
int main(void)
{
	while(~scanf("%d",&n))
	{
		int i;
		
		__int64 ans=0;
		memset(c,0,sizeof(c));
		for(i=1;i<=n;i++)
		{
			int x;
			scanf("%d",&x);
			update(x,1,x);
			__int64 k1=i-getsum_index(x);
			if(k1!=0)
			{
				__int64 k2=getsum_sum(n)-getsum_sum(x);
				ans=ans+k1*x+k2;
			}
		
		}
		printf("%I64d/n",ans);
	}
}

思路:对于当前数X,我们如果知道前面比它大的数有多少,假设为K,那么有部分代价是确定的,那就是K*X;然后还得加上比它大的那些数之和,这就是当数列到X为止,排好所需要的最小代价。

求比它大的数的个数就是求逆序数,用树状数组完美解决,K1即是逆序对数(一定要__int64),接下来就是求总和,我们可以用get_sum(n)与get_sum(x)的差来表示(题目中数的范围为1-N)。

解题参考:http://blog.csdn.net/me4546/article/details/6333225