HDU - 3015 Disharmony Trees

题意：给你n棵树的坐标x，高度h，让你分别按坐标，高度排序后，得到一新的序列，也可以理解为一颗组合成的新树，这棵树的坐标，高度都是排序来的，看了别人的解释，还是理解了老半天，然后就是求花费了，每任意两颗树的花费为

min(h[i],h[j])*abs(x[i]-x[j])，求所有组合的花费

思路：经过排序的处理后，就是仿着POJ-1990 的思想来做 了，也可以简化成：按高度排序后，然后按每棵树来处理，将小于它的高度和大于它的高度计算进去，这就需要一个变量记录到目前为止的总的高度和

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 100005;
#define ll long long 

struct node{
	int x,h;
}a[MAXN],v[MAXN];
ll c[2][MAXN];
int Max,idx[MAXN];

int cmp(const void *a,const void *b){
	node A = *(node *) a;
	node B = *(node *) b;
	return B.h - A.h;
}

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

void add(int p,int d,int k){
	while (p < MAXN){
		c[k][p] += d;
		p += lowbit(p);
	}
}

ll sum(int p,int k){
	ll ans = 0;
	while (p > 0){
		ans += c[k][p];
		p -= lowbit(p);
	}
	return ans;
}

void init(node d[],int n){
	qsort(d,n,sizeof(d[0]),cmp);
	idx[d[n-1].x] = 1;
	for (int i = n-2; i >= 0; i--)
		if (d[i].h == d[i+1].h)
			idx[d[i].x] = idx[d[i+1].x];
		else idx[d[i].x] = n-i;
}

int main(){
	int n;
	ll ans,lown,lows,pres;
	while (scanf("%d",&n) != EOF){
		Max = n;
		for (int i = 0; i < n; i++)
			scanf("%d%d",&a[i].x,&a[i].h);
		for (int i = 0; i < n; i++){
			v[i].x = i;
			v[i].h = a[i].x;
		}
		init(v,n);
		for (int i = 0; i < n; i++)
			a[i].x = idx[i];
		for (int i = 0; i < n; i++){
			v[i].x = i;
			v[i].h = a[i].h;
		}
		init(v,n);
		for (int i = 0; i < n; i++)
			a[i].h = idx[i];
		qsort(a,n,sizeof(a[0]),cmp);
		ans = pres = 0;
		memset(c,0,sizeof(c));
		for (int i = 0; i < n; i++){
			lown = sum(a[i].x-1,0);
			lows = sum(a[i].x-1,1);
			ans += a[i].h * (2*lown*a[i].x-i*a[i].x+pres-2*lows);
			add(a[i].x,1,0);
			add(a[i].x,a[i].x,1);
			pres += a[i].x;
		}
		cout << ans << endl;
	}
	return 0;
}

HDU - 3015 Disharmony Trees,布布扣,bubuko.com

HDU - 3015 Disharmony Trees

原文：http://blog.csdn.net/u011345136/article/details/23095325