其实,我英语水平垃圾的很。。。
题目大意:
给你坐标和每个坐标的权值,题目求n个坐标两两之间的“声音权值”的和,其中任意两个点之间的“声音权值” = 距离*max(两点的权值)。
1.暴力求解法:容易想,也容易TLE
2.树状数组:
我们在处理的过程中,按照权值大小升序排序,可以省略掉取max的步骤。
对于排序之后的第i个元素,设坐标为,权值为
,那么对于任意的
,都有
,在处理第i个元素的时候,权值都是取的
。其中,权值小于
的点有
个,设他们在集合
中。
但是这样之后,坐标x是无序的,设中坐标小于
的点有
个,坐标的和是
;
大于的就有
个,(中间要去掉一个本身),坐标的和是
然后求距离,坐标小于的点的距离和是
,坐标大于
的点的距离和是
,权值和就是
。
这个过程其实是可以转化为区间和的,例如,求中坐标小于
的坐标和
,其实就是以坐标为树状数组的下标,求
的区间和。其他详细看代码。
code:
//#include <bits/stdc++.h> #include <iostream> #include <cstdio> #include <algorithm> using namespace std; typedef long long ll; typedef unsigned long long ull; const int N = 20000+5; //const ll inf=0x3f3f3f3f3f3f3f3f; const int inf=0x3f3f3f3f; const int mod = 199999; const double eps=1e-7; //const int tmp=31; int sn[N],sx[N];//坐标和,坐标数量 struct node { int v,x; bool operator<(const node& b)const{ return v<b.v; } }a[N]; int lowebit(int x){ return x&(-x); } void add(int i,int v){ while(i<=20000){ sx[i]+=v; sn[i]++; i+=lowebit(i); } } ll ask(int i,int op){//op是0的时候计算坐标和,1的时候计算坐标数量 ll s=0; while(i>0){ if(!op) s+=sx[i]; else s+=sn[i]; i-=lowebit(i); } return s; } int main() { int n; scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d%d",&a[i].v,&a[i].x); sort(a+1,a+n+1); ll s=0; for(int i=1;i<=n;i++){ ll cor=ask(a[i].x,0); ll cor2 = ask(20000,0);//x的最大值是20000,所以用它当作区间的右端点, //最后减去小于a[i].x的坐标和,剩下的才是真正大于a[i].x的坐标和,之后再求距离。 ll num=ask(a[i].x,1); s += a[i].v*(num*a[i].x-cor)+a[i].v*(cor2-cor-(i-num-1)*a[i].x); add(a[i].x,a[i].x); } printf("%lld\n",s); return 0; }
poj不支持万能头文件!!!