原題鏈接 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;}新聞熱點
疑難解答
