POJ 1990 MooFest

本文主要是介绍POJ 1990 MooFest，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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头牛，不同的听力值v，当i,j想要通话时，需要max(v(i),v(j))(dist[i]-dist[j])的volume，问这n(n-1)/2对牛总共的volume时多少。
分析：
按v从小到大排序，对于每一头牛，只看他前面的，则只需要处理出距离之和。然而，左右不同，所以分开处理，记录左面的（右面的可以推出来），需要记录个数和坐标。

---

#include<algorithm>
#include<iostream>
#include<cstdio>
using namespace std;
const int maxn=20005;
long long n,ans,num[2][maxn];
struct cow
{long long x,v;
}aa[maxn];
bool cmp(cow c,cow d)
{return c.v<d.v;
}
long long lowbit(long long x)
{return x&(-x);
}
void chg(long long pos,long long x,int k)
{while(pos<=20000){num[k][pos]+=x;pos+=lowbit(pos);}
}
long long rsum(long long pos,int k)
{int sum=0;while(pos>0){sum+=num[k][pos];pos-=lowbit(pos);}return sum;
}
int main()
{scanf("%lld",&n);for(int i=1;i<=n;i++)scanf("%lld%lld",&aa[i].v,&aa[i].x);sort(aa+1,aa+n+1,cmp);for(int i=1;i<=n;i++){long long a=rsum(aa[i].x,0),b=rsum(aa[i].x,1);//a 左个数，b 左坐标和 ans+=(aa[i].x*a-b+rsum(20000,1)-b-(i-1-a)*aa[i].x)*aa[i].v;chg(aa[i].x,1,0);chg(aa[i].x,aa[i].x,1);}printf("%lld\n",ans);return 0;
}

这篇关于POJ 1990 MooFest的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---