Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
没事干发份解题报告//任意头牛油两个属性Vi和Xi,问题要求所有的点对和sum(max(vi,vj)*|xi-xj|) //首先按V从小到大排,这样就解决了最大的问题,以V的大小阶段性来处理累加和 //每次统计当前情况下声音比V小的那些点的坐标距离和,以及比声音V小,且x比它小的点的个数 //num=sum(|xi-xj|*vi)(j<i) //转化下,即axi-sum1+sum2-bxi //其中a表示比当前点x小的点个数,sum1表示比当前点x小的点的坐标和 //b表示比当前点x大的点个数,sum2表示比当前点x大的点的坐标之和 //得到这样一个式子:query1(xi-1)*xi-query2(xi-1)+query2(20000)-query2(xi)-(query1(20000)-query1(xi))*xi //最后乘以vi,累加起来即可 Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator