首页 > 代码库 > POJ 1990 MooFest 树状数组
POJ 1990 MooFest 树状数组
这题是我看了大白书树状数组后刷的第一道题，确实难度不小，所以只好上网找题解了，网上的做法确实精彩。这题的题意主要是有N头牛，每两头牛之间交流的费用为它们的距离乘上两者音量的最大值（即max(v(i),v(j))），然后统计所有牛两两交流的总费用。一开始能想到的做法便是O(n2)的暴力枚举了，当时的我也只能想到这样的复杂度，很纳闷怎么能和树状数组搭上边呢？然后看了别人的题解后才惊叹其思路之妙。
在博客 http://www.cnblogs.com/Fatedayt/archive/2011/10/08/2202439.html 上说得很详细，附上其主要的思路：
已经说得很详细了，即统计某头牛i 时，通过排序和预处理可以把原本的O(n)查询下降到O(logn)，确实很厉害，也很难想到。我结合网上其他人的题解半抄半改写出如下代码：
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 typedef long long LL; 6 const int maxn= 20020; 7 8 inline LL lowbit(LL x) { return x&(-x); } 9 10 struct treeArray{11 LL c[maxn], n;12 treeArray(LL n= 0): n(n) { memset(c,0,sizeof(c)); }13 LL sum(LL x) {14 LL ans= 0;15 while(x){16 ans+= c[x];17 x-= lowbit(x);18 }19 return ans;20 }21 void add(LL x, LL d){22 while(x<=n){23 c[x]+= d;24 x+= lowbit(x);25 }26 }27 } Count(20003),dist(20003);28 29 struct Cow{30 LL v,x;31 bool operator <(const Cow c2) const {32 return v<c2.v;33 }34 } cow[maxn];35 36 int main(){37 int n,i;38 scanf("%d",&n);39 for(i=1; i<=n; ++i)40 scanf("%lld%lld",&cow[i].v,&cow[i].x);41 sort(cow+1,cow+n+1);42 LL ans= 0, alldist= 0;43 for(i=1; i<=n; ++i){44 LL x = cow[i].x;45 LL num = Count.sum(x);46 LL lessdist = dist.sum(x);47 ans += cow[i].v*(num*x-lessdist+alldist-lessdist-(i-1-num)*x);48 Count.add(x,1);49 dist.add(x,x);50 alldist += x;51 }52 printf("%lld\n",ans);53 return 0;54 }
其中，Count.sum(x)表示统计比x小的牛的个数（在上图中就是a），dist.sum(x)表示统计比x小的牛的位置之和（在上图中为b）；alldist即前i 头牛的所有距离（可以认为是以原点作为标准），其余的变量名也不难理解。码完后才感到树状数组真是太强大了，不得不赞！
POJ 1990 MooFest 树状数组
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。