首页 > 代码库 > POJ 1990 MooFest --树状数组
POJ 1990 MooFest --树状数组
题意：牛的听力为v，两头牛i,j之间交流，需要max(v[i],v[j])*dist(i,j)的音量。求所有两两头牛交谈时音量总和∑(max(v[i],v[j])*abs(x[j]-x[i])) ，x[i]表示i的坐标
解法：将牛按听力从小到大排序，这样就可以使每次算一头牛与别的牛的值时听力永远取自己的听力。
建两棵树状数组，一颗维护牛的坐标，一颗维护牛的个数。
当遍历到某头牛 i 时，求出它的左边有多少头牛，记为L，右边记为R，并且算出左边的坐标之和Lsum,右边坐标值的和Rsum。
那么此时 总的和要加上 (L*x[i]-Lsum)*V[i] （左边） + (Rsum-R*x[i])*V[i] （右边）， 仔细想想就知道了。
代码：
#include <iostream>#include <cstdio>#include <cstring>#include <cstdlib>#include <cmath>#include <algorithm>using namespace std;#define N 20007int c[N],cnt[N],n,maxi;struct node{ int val,x;}p[N];int cmp(node ka,node kb) { return ka.val < kb.val; }int lowbit(int x) { return x&-x; }void modify(int *c,int x,int val){ while(x <= maxi) c[x] += val, x += lowbit(x);}int getsum(int *c,int x){ int res = 0; while(x > 0) { res += c[x]; x -= lowbit(x); } return res;}int main(){ int i,j; while(scanf("%d",&n)!=EOF) { maxi = 0; for(i=1;i<=n;i++) scanf("%d%d",&p[i].val,&p[i].x), maxi = max(maxi,p[i].x); sort(p+1,p+n+1,cmp); memset(c,0,sizeof(c)); memset(cnt,0,sizeof(cnt)); lll sum = 0; for(i=1;i<=n;i++) { int L = getsum(cnt,p[i].x); int R = getsum(cnt,maxi) - getsum(cnt,p[i].x-1); int Lsum = getsum(c,p[i].x); int Rsum = getsum(c,maxi) - getsum(c,p[i].x-1); sum += 1LL*(p[i].x*L-Lsum)*p[i].val; sum += 1LL*(Rsum-p[i].x*R)*p[i].val; modify(c,p[i].x,p[i].x); modify(cnt,p[i].x,1); } cout<<sum<<endl; } return 0;}
POJ 1990 MooFest --树状数组
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。