首页 > 代码库 > （POJ 1990）Mowfest（确定不再来一发树状数组么？）

（POJ 1990）Mowfest（确定不再来一发树状数组么？）

2024-11-22 14:36:02   202人阅读

MooFest
Time Limit: 1000MS Memory Limit: 30000K
Total Submissions: 8177 Accepted: 3691

Description

Every year, Farmer John‘s N (1 <= N <= 20,000) cows attend "MooFest",a social gathering of cows from around the world. MooFest involves a variety of events including haybale stacking, fence jumping, pin the tail on the farmer, and of course, mooing. When the cows all stand in line for a particular event, they moo so loudly that the roar is practically deafening. After participating in this event year after year, some of the cows have in fact lost a bit of their hearing. 

Each cow i has an associated "hearing" threshold v(i) (in the range 1..20,000). If a cow moos to cow i, she must use a volume of at least v(i) times the distance between the two cows in order to be heard by cow i. If two cows i and j wish to converse, they must speak at a volume level equal to the distance between them times max(v(i),v(j)). 

Suppose each of the N cows is standing in a straight line (each cow at some unique x coordinate in the range 1..20,000), and every pair of cows is carrying on a conversation using the smallest possible volume. 

Compute the sum of all the volumes produced by all N(N-1)/2 pairs of mooing cows. 

Input

* Line 1: A single integer, N 

* Lines 2..N+1: Two integers: the volume threshold and x coordinate for a cow. Line 2 represents the first cow; line 3 represents the second cow; and so on. No two cows will stand at the same location. 

Output

* Line 1: A single line with a single integer that is the sum of all the volumes of the conversing cows. 

Sample Input

43 12 52 64 3

Sample Output

57


大体题意就不多说了，要注意的就是题目要算的值是每两头牛交流需要的最小音量加和。

先看下数据，用暴力枚举的话铁定超时，仔细分析后发现，两头牛要想交流，声音大小由两个因素决定：距离和听力的最大值。
依照Japan那道题的思想，依然可以把这两个条件转化为一个条件。即提前把所有牛按照听力大小排序，这样在计算一头牛与在他前面牛的说话声音时，声音一定会取它自己的声音值，这样一边维护一边遍历一遍，对于每头牛只考虑在它之前的牛，就能得到答案。

那么问题来了，如何计算这头牛与它之前牛交流声音的总和呢，因为数据较大，算嘉和的时候就需要用到树状数组来减小时间复杂度。
开两个树状数组，一个用来存每个位置的牛出现次数，另一个用来存其对应区域的x坐标加和值；
在计算每一个节点时，就可以通过提取公因数分别算出与其后面的、前面的牛声音大小的总和。这样遍历到结尾就可以知道结果了。

PS：坑点在于数据精度要求较高，需要用long long(马丹...)

#include<iostream>#include<cstdio>#include<vector>#include<set>#include<map>#include<string.h>#include<cmath>#include<algorithm>#include<queue>#define LL long long#define inf 0x3f3f3f3fusing namespace std;struct aa{    long long x,y;    bool operator <(const aa &other)const    {        return x<other.x;    }};LL c1[20010];//记录出现位置有多少头牛LL c2[20010];//记录前i位置牛位置和aa a[20010];LL l,r;LL lowbit(LL i){    return i&(-i);}void update(LL *c,LL i,LL p){    while(i<=r)    {        c[i]+=p;        i+=lowbit(i);    }}LL sum(LL *c,LL i){    LL s=0;    while(i>=l)    {        s+=c[i];        i-=lowbit(i);    }    return s;}int  main(){    int n;    while(~scanf("%d",&n))    {        memset(c1,0,sizeof(c1));        memset(a,0,sizeof(a));        memset(c2,0,sizeof(c2));        l=0x3f3f3f3f;        r=0;        for(int i=1;i<=n;i++)        {             scanf("%I64d%I64d",&a[i].x,&a[i].y);             l=min(l,a[i].y);             r=max(r,a[i].y);        }            sort(a+1,a+1+n);        LL ans=0;        for(int i=1;i<=n;i++)        {            update(c1,a[i].y,1);            update(c2,a[i].y,a[i].y);            ans+=(sum(c2,r)-sum(c2,a[i].y)-(sum(c1,r)-sum(c1,a[i].y))*a[i].y)*a[i].x;            ans+=(sum(c1,a[i].y-1)*a[i].y-sum(c2,a[i].y-1))*a[i].x;        }        printf("%I64d\n",ans);    }    return 0;}

 

（POJ 1990）Mowfest（确定不再来一发树状数组么？）


联系
我们