本文主要是介绍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的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
