xindoo is
always here

poj 1990 MooFest 树状数组


题意就是有N头牛,每头牛都有一个坐标和声调值(x, v),两头牛之间通讯要花费的能量是他们的距离乘以最大的一个音调值,现在要任意两头牛之间都相互通讯一次,求总共需要花费多少能量?

      显然总共有n*(n+1)/2条,我们可以用树状数组保存,树状数组很适合求区间的和,我们只需要求出某头牛左右两边分别有多少头牛比它的音调小,且他们的坐标和,这样我们就能求出这头牛到其他牛之间的距离和了,因为它的音调值已知且在这先中最大,然后这要求出一头牛与其他比他小的通讯花费的能量了,然后以此求出其他的。这样计算出了它小的,遍历一遍后必然每头牛之间都有里通讯。

#include<iostream>
#include<algorithm>
#define lowbit(x) (x&(-x))
using namespace std;
const int MAX = 20005;
 
struct data{
    int x, w;
}cow[MAX];
int arNum[MAX], arDis[MAX];
 
bool cmp(data a, data b){
    return a.x < b.x;
}
 
void add(int i, int *ar, int w){
    while(i <= MAX-1){
        ar[i] += w;
        i += lowbit(i);
    }
}
 
__int64 sum(int i, int *ar){
    __int64 ans = 0;
    while(i > 0){
        ans += ar[i];
        i -= lowbit(i);
    }
    return ans;
}
 
int main(){
    int n, i;
    __int64 preNum, preDis;
    scanf("%d", &n);
    for(i = 0; i < n; i ++)
        scanf("%d%d", &cow[i].w, &cow[i].x);
    sort(cow, cow + n, cmp);
    __int64 ans = 0;
    memset(arNum, 0, sizeof(arNum));          //  求向左的总能量。
    memset(arDis, 0, sizeof(arDis));
    for(i = 0; i < n; i ++){
        preNum = sum(cow[i].w-1, arNum);
        preDis = sum(cow[i].w-1, arDis);
        ans += (preNum * cow[i].x - preDis) * cow[i].w;
        add(cow[i].w, arNum, 1);
        add(cow[i].w, arDis, cow[i].x);
    }
    memset(arNum, 0, sizeof(arNum));          //  求向右的总能量。
    memset(arDis, 0, sizeof(arDis));
    for(i = n-1; i >= 0; i --){
        preNum = sum(cow[i].w, arNum);        //  这里不要用w-1,考虑了声调相等的情况。
        preDis = sum(cow[i].w, arDis);
        ans += (preDis - preNum * cow[i].x) * cow[i].w;
        add(cow[i].w, arNum, 1);
        add(cow[i].w, arDis, cow[i].x);
    }
    printf("%I64d\n", ans);
    return 0;
}
打赏
未经允许不得转载:XINDOO » poj 1990 MooFest 树状数组
分享到: 更多 (0)

评论 抢沙发

xindoo

联系我联系我们

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏