随笔 - 97, 文章 - 22, 评论 - 81, 引用 - 0
数据加载中……

PKU 1990 MooFest

题目链接:http://poj.org/problem?id=1990

/*
题意:
    约翰农夫有N(N <= 20000)头牛,每头牛有一个权值Vi,他将它们排成一排,
牛i和牛j的阈值是  两者的距离差*max(Vi, Vj),现在给出每头牛的权值和它的
位置,求所有两头牛之间的阈值之和。

题解:
    树状数组

思路:
    我们准备两个树状数组,以每头牛的位置作为树状数组的下标,其中一个用
来表示当前位置的牛的位置的值,另一个则记录当前位置牛的个数,然后对所有
牛以Vi为关键字进行递增排序。
    接下来对每头牛进行一次线扫,首先统计比当前这头牛的位置小的和大的牛
的数目和位置和,然后做差求出以当前牛的权值为最大值的阈值总和。之后将这
头牛的数量和位置插入到树状数组中进行更新。
*/


#include 
<iostream>
#include 
<algorithm>

using namespace std;

#define maxn 20010
#define ll __int64

struct point {
    
int V;
    
int pos;
}
pt[maxn];

ll c[
2][maxn];
int n, Max;

ll ABS(ll v) 
{
    
return v < 0 ? -v : v;
}


int cmp(point a, point b) {
    
return a.V < b.V;
}


int lowbit(int x) {
    
return x & (-x);
}


void add(int idx, int pos, int v) {
    
while(pos <= Max) {
        c[idx][pos] 
+= v;
        pos 
+= lowbit(pos);
    }

}


ll sum(
int idx, int pos) {
    ll s 
= 0;
    
while(pos > 0{
        s 
+= c[idx][pos];
        pos 
-= lowbit(pos);
    }

    
return s;
}



int main() {
    
int i;
    
while(scanf("%d"&n) != EOF) {
        Max 
= 0;
        
for(i = 0; i < n; i++{
            scanf(
"%d %d"&pt[i].V, &pt[i].pos);
            
if(pt[i].pos > Max)
                Max 
= pt[i].pos;
        }


        
for(i = 1; i <= Max; i++)
            c[
0][i] = c[1][i] = 0;
        sort(pt, pt 
+ n, cmp);

        ll ans 
= 0;
        
for(i = 0; i < n; i++{
            ans 
+= ABS((sum(0, Max) - sum(0, pt[i].pos)
                 
- (sum(1, Max) - sum(1, pt[i].pos)) * pt[i].pos)) * pt[i].V;

            ans 
+= ABS((sum(0, pt[i].pos)
                 
- sum(1, pt[i].pos) * pt[i].pos)) * pt[i].V;

            add(
0, pt[i].pos, pt[i].pos);
            add(
1, pt[i].pos, 1);
        }

        printf(
"%I64d\n", ans);
    }

    
return 0;
}

posted on 2011-04-09 22:06 英雄哪里出来 阅读(1088) 评论(0)  编辑 收藏 引用 所属分类: 树状数组


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理