|
|
题目大意：
有N头牛，站在X轴上，没有共点的情况，每个牛有一个听力值V(i)，他们交流所消耗的最少volume为abs（X（i）-（X（j）））*MAX{V（i）,V（j）}
最后再求总和。
由于数据量最大为20000,显然O(n^2)的算法会超时。先按V值进行从小到大排序可解决MAX的问题，最后就是对每头牛求V值小于他的权值了。
对于第i个牛，在0~i-1中，用两个数状数组，a表示坐标小于x[i]的个数，b表示坐标小于x[i]的牛的坐标之和，另外c表示0~i-1中所有牛的坐标之和。
 
1 long long solve()
2 {
3 long long ans=0,c=dd[0].id;
4
5 update(a,dd[0].id,1);
6 update(b,dd[0].id,dd[0].id);
7
8 long long p,q;
9  for(int i=1;i<n;i++){
10 p=get_sum(a,dd[i].id);
11 q=get_sum(b,dd[i].id);
12 ans+=dd[i].v*(dd[i].id*p-q+(c-q)-dd[i].id*(i-p));
13 update(a,dd[i].id,1);
14 update(b,dd[i].id,dd[i].id);
15 c+=dd[i].id;
16 }
17 return ans;
18 }
|