MooFest Time Limit: 1000MS Memory Limit: 30000K Total Submissions: 7716 Accepted: 3474 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 Source
USACO 2004 U S Open
题意： 有n只牛在数轴上排成一排，每只牛都在两个属性v,x v表示说话的声音，x表示牛的位置 当两只牛i,j要进行交谈时,他们产生的声音是 dis(xi,xj)*max(vi,vj) : dis表示两个值的差的绝对值 问你要是任意两只牛进行交谈，他们总共产生的声音为多少？
分析：
由于两只牛说话的声音是max(vi,vj)，所以我们可以按照v的升序来将牛排序，那么就可以保证当牛i和他前面的牛进行交谈时，是以vi来交谈的
我们现在只需要求出i和在他前面的所有的牛的位置的差值的总和就可以 了
我们将前面的牛分为两类：在前面且x比xi小的，和在前面x不小于xi的 我们假设 cnt为前面x比xi小的牛的个数 presume为前面x比xi小的牛的x的总和 total[i-1]表示前面i-1只牛的x的总和 那么i牛和在它前面且x比xi小的牛的差值的总和为 cnt * xi - presum 并且我们知道前面x不比xi小的牛的个数为 i-1 - cnt i牛和在它前面且x不比xi小的牛的差值的总和为 total[i-1] - presum - (i-1 - cnt) * xi) 所以牛i产生的声音为 cnt * xi - presum + total[i-1] - presum - (i-1 - cnt) * xi) * vi
所以我们只需要用树状数组来维护 cnt 和 presume 即可
AC代码：
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> using namespace std; const int maxn = 20010; int c[maxn],d[maxn],total[maxn]; int n; struct Node { int v,x; }node[maxn]; int lowbit(int x) { return x & (-x); } void update(int x) { int t = x; while( x <= maxn) { c[x]++; d[x] += t; x += lowbit(x); } } int getsum_c(int x) { int sum = 0; while(x > 0) { sum += c[x]; x -= lowbit(x); } return sum; } int getsum_d(int x) { int sum = 0; while(x >0) { sum += d[x]; x -= lowbit(x); } return sum; } int cmp(Node a,Node b) { return a.v < b.v; } int main() { scanf("%d",&n); memset(c,0,sizeof(c)); memset(d,0,sizeof(d)); memset(total,0,sizeof(total)); for(int i=0;i<n;i++) scanf("%d%d",&node[i].v,&node[i].x); sort(node,node+n,cmp); long long ans = 0; for(int i=0;i<n;i++) { if(i == 0) { total[i] = node[i].x; update(node[i].x); } else { total[i] = total[i-1] + node[i].x; int cnt = getsum_c(node[i].x); int presum = getsum_d(node[i].x); ans += (1LL * node[i].v * (cnt * node[i].x - presum + total[i-1] - presum - (i - cnt) * node[i].x)); update(node[i].x); } } printf("%lld",ans); return 0; }