先排序,将那些牛按照 v 从小到大排序,这样的话,对于某只来说,和排在前面的牛说话的话所用的音量必然就是他自己的v 了。
然后,只要求出排在某个牛之前的牛到他的总距离即可,因为我们的题目要求的就是求声音乘以距离 然后再求和。
考虑到这是要求某个区间的和,显然就是用树状数组啊……
刚好之前已经排好序了,我们将牛的坐标存在数组中,利用树状数组求和。
数据比较大,C++得用long long来存储数据,血的教训啊!
最后printf输出得用I64d 妥妥的。
AC Memory : 996 KB Time : 79 ms
代码:
#include <fstream> #include <cstdio> #include <iostream> #include <algorithm> #include <cstring> #define lowbit(x) (x&(-x)) using namespace std; const int kMAX=20010; int count_sum[kMAX],pos_sum[kMAX]; long long sum(int x,const int *c) { long long s=0; for(int i=x;i>0;i-=lowbit(i)) s+=c[i]; return s; } void updata(int x,const int var,int *c) { for(int i=x;i<kMAX;i+=lowbit(i)) c[i]+=var; } struct NODE { int pos,var; inline bool operator<(const NODE &tmp) const { return var<tmp.var; } }node[kMAX]; int main(void) { int n; while(~scanf("%d",&n) && n) { for(int i=0;i<n;++i) { scanf("%d%d",&node[i].var,&node[i].pos); } sort(node,node+n); memset(count_sum,0,sizeof(count_sum)); memset(pos_sum,0,sizeof(pos_sum)); long long ans=0; long long total=node[0].pos; updata(node[0].pos,1,count_sum); updata(node[0].pos,node[0].pos,pos_sum); for(int i=1;i<n;++i) { long long left_count=sum(node[i].pos,count_sum); long long left_sum = sum(node[i].pos,pos_sum); long long left_total = node[i].pos * left_count - left_sum; long long right_total = total - left_sum - (i-left_count)*node[i].pos; ans+=(left_total+right_total)*node[i].var; updata(node[i].pos,1,count_sum); updata(node[i].pos,node[i].pos,pos_sum); total+=node[i].pos; } printf("%I64d\n",ans); } return 0; }