首页 > 代码库 > POJ 1990——MooFest（2个树状数组）

POJ 1990——MooFest（2个树状数组）

2024-07-19 23:42:15   222人阅读

MooFest
Time Limit: 1000MS Memory Limit: 30000K
Total Submissions: 5235 Accepted: 2260

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

4
3 1
2 5
2 6
4 3

Sample Output

57

————————————————————分割线——————————————


题目大意：

给定n头牛的听力和坐标，每两头牛交谈需要（max（v（i），v（j) )*abs(dis[i]-dis[j])),n头牛总共要交谈（n*（n-1）/2）次


思路：

对牛的听力进行从小到大排序，那么对于第i头牛 交谈，需要计算

1：坐标比第i头牛小的牛的数量 a，坐标和b

2：坐标比第i头牛大的牛的数量 c，坐标和d

那么第i头牛交谈总共需要：

(d-c*a[i].y+a*a[i].y-b)*a[i].x


#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#define M 20000+10
#define ll __int64
using namespace std;
ll b[M],c[M];
struct node
{
    int x,y;
    bool operator<(const node&a)const
    {
        return x<a.x;
    }
}a[M];
void update(int x,int v,ll *h)
{
    for(int i=x;i<=M;i+=i&-i){
        h[i]+=v;
    }
}
ll getsum(int x,ll *h)
{
    ll sum=0;
    for(int i=x;i>0;i-=i&-i){
        sum+=h[i];
    }
    return sum;
}
int main()
{
    int n;
    scanf("%d",&n);
    memset(b,0,sizeof(b));
    memset(c,0,sizeof(c));
    for(int i=1;i<=n;++i){
        scanf("%d %d",&a[i].x,&a[i].y);
    }
    sort(a+1,a+1+n);
    ll ans=0;
    for(int i=1;i<=n;++i){
        ll x1=(ll)(getsum(a[i].y,b)*a[i].y-getsum(a[i].y,c));
        ll x2=(ll)(getsum(M,c)-getsum(a[i].y,c)-(i-1-getsum(a[i].y,b))*a[i].y);
        ans+=(ll)(x1+x2)*a[i].x;
        update(a[i].y,1,b);
        update(a[i].y,a[i].y,c);
    }
    printf("%I64d\n",ans);
    return 0;
}




POJ 1990——MooFest（2个树状数组）


联系
我们