Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
北京大学《ACM/ICPC大学生程序设计竞赛训练》暑期课面向全球招生!

没事干发份解题报告

Posted by foreverlin at 2009-07-28 20:01:54 on Problem 1990
//任意头牛油两个属性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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator