POJ-1990 MooFest---两个树状数组-白红宇

POJ-1990 MooFest---两个树状数组

阅读量：5998 次

发布时间：2019-06-20

本文共 1376 字，大约阅读时间需要 4 分钟。

题目链接：

题目大意：

一群牛参加完牛的节日后都有了不同程度的耳聋，第i头牛听见别人的讲话，别人的音量必须大于v[i]，当两头牛i，j交流的时候，交流的最小声音为max{v[i],v[j]}*他们之间的距离。现在有n头牛，求他们之间两两交流最少要的音量和。

解题思路：

使用树状数组，首先将二元组按照v的大小从小到大排序，这样可以保证每头牛比前面的牛的v大，计算它和它前面牛的音量和的时候，就可以直接用该头牛的v，还需要计算出|a[i].x - x|绝对值之和。

用树状数组维护坐标x，可以直接求出比这头牛小的所有x之和，还需要用另一个树状数组维护每个元素出现的次数，直接求出小于这头牛的x的牛的数目。

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
          6 #include
          
            7 #include
           
             8 #include
            
              9 #include
             
              10 #include
              
               11 #define lowbot(i) (i&(-i))12 using namespace std;13 typedef long long ll;14 const int maxn = 1e5 + 10;15 struct cow16 {17 ll v, x;18 bool operator <(const cow& a)const19 {20 return v < a.v || v == a.v && x < a.x;21 }22 }a[maxn];23 int tree[maxn], id_num[maxn];24 void add(int x, int d, int tree[])25 {26 while(x <= maxn)//上限是maxn27 {28 tree[x] += d;29 x += lowbot(x);30 }31 }32 ll sum(int x, int tree[])33 {34 ll ans = 0;35 while(x)36 {37 ans += tree[x];38 x -= lowbot(x);39 }40 return ans;41 }42 int main()43 {44 int n;45 scanf("%d", &n);46 for(int i = 0; i < n; i++)scanf("%lld%lld", &a[i].v, &a[i].x);47 sort(a, a + n);48 ll num, tot, ans = 0;49 for(ll i = 0; i < n; i++)50 {51 num = sum(a[i].x, id_num);52 tot = sum(a[i].x, tree);53 ans += (num * a[i].x - tot) * a[i].v;54 //cout<
               
                <<" - "<
                
                 <<" + "<
                 
                  <

转载于:https://www.cnblogs.com/fzl194/p/8955028.html

你可能感兴趣的文章