原题链接 MooFest Time Limit: 1000MS Memory Limit: 30000K Total Submissions: 7357 Accepted: 3299 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。两牛交流需要音量为distance * max(v(i),v(j))，求所有牛两两交流所需总和？ 思路：将奶牛的耳背程度按照升序排列后，从小到大取的话每一次都是已经有的奶牛里最耳背的，就只需要将之前所有的奶牛距离*该奶牛的耳背程度即可，结果就是所有的乘积的加和。比如对于样例来说将最不耳背的奶牛放入后，我们可以通过后面的三个操作得到结果
res += 2 * (|6-5|)res += 3 * (|1-5| + |1-6|)res ++ 4 * (|2-1| + |2-5| + |2-6|)我们通过观察可以得到一个通式
res += v[i] * (x[i] * 小于等于x[i]的元素个数 - 小于等于x[i]的元素的位置和 - x[i] * 大于x[i]的元素个数 + 大于x[i]的元素的位置和)
我们明显经常用到求区间和的操作，那么我们就可以使用树状数组来快速地实现求区间和的操作。建立一个奶牛个数的BIT数组，和位置和的BIT数组
#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>using namespace std;const int maxn = 20000 + 10;typedef long long ll;pair<ll,ll> a[maxn];//first代表音量v，second代表位置xvoid add(ll *bit,ll x,ll m){ while(x<maxn){ bit[x] += m; x += (x & -x); }}ll sum(ll *bit,ll x){ ll s=0; while(x>0){ s += bit[x]; x -= (x & -x); } return s;}int main(){ ll bita[maxn],bitb[maxn],n;//分别代表位置小于等于a[i].x的元素的个数和这些元素的位置和 ll res = 0; memset(bita,0,sizeof(bita)); memset(bitb,0,sizeof(bitb)); scanf("%lld",&n); for(int i=0;i<n;i++) scanf("%lld%lld",&a[i].first,&a[i].second); sort(a,a+n); add(bita,a[0].second,1); add(bitb,a[0].second,a[0].second); for(int i=1;i<n;i++){ ll lowbitasum=sum(bita,a[i].second); ll lowbitbsum=sum(bitb,a[i].second); //res += a[i].first * (a[i].second*lowbitasum - lowbitbsum - a[i].second*(sum(bita,maxn-1)-lowbitasum) + (sum(bitb,maxn-1)-lowbitbsum)); res += a[i].first * (a[i].second * (lowbitasum*2 - sum(bita,maxn-1)) - lowbitbsum*2 + sum(bitb,maxn-1)); add(bita,a[i].second,1); add(bitb,a[i].second,a[i].second); } cout << res << endl; return 0;}新闻热点
疑难解答
