首页 > 代码库 > POJ 1990 MooFest 树状数组

POJ 1990 MooFest 树状数组

2024-08-07 20:18:02   218人阅读

　　这题是我看了大白书树状数组后刷的第一道题，确实难度不小，所以只好上网找题解了，网上的做法确实精彩。这题的题意主要是有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 树状数组


联系
我们