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大学生程序设计竞赛训练》暑期课面向全球招生!

终于A了,说下思路和一些注意点

Posted by Findxiaoxun at 2013-07-27 16:35:48 on Problem 1990
首先,最重要的是理解好题意:1.两头牛只要通讯一次就行。每次的耗费是distance*max(v[i],v[j])2.按power还是按position排序。我选的是power,因为position没有重复值。排序这个想法跟Japan那道题是一样的。
说下思路:
按照power的升序排好后,依次加入树状数组,每加一次,就查一次,累计一次ans。这个是标准的数组数组的解法。
但是,树状数组的索引值是牛的坐标的索引值,这就意味着,能力比当前低的牛可能会排到其后面,而且,它们的距离值是需要的。
这就要求,既能记录到前面有多少头牛,又能记录他们的距离和,后面有多少头牛,和他们的距离和。
而想到,加点的时候,有一个i来控制,也就是说,在i前面   有    a头牛的话,后面有i-a头,顺着这个想法,那也可以统计坐标和啊。前面加了i头牛,总共的坐标和distance可以累加出来,而在i的坐标前面有(这里的有和加是两回事)的牛的坐标和为sum(data[i].position-1).dist,那么坐标在第i个的后面,而且power比第i个的小的坐标和就是distance-sum(data[i].position-1).dist
因为是按照power排的序,所以在i前面加的power都比第i个小,也就是说,如果之前加的和第i个通讯的话,取的power指肯定是第i个的
公式:
这里的sum(data[i].position).num表示坐标在data[i].position前面的牛的个数
sum(data[i].position-1).dist    i的坐标前面有(这里的有和加是两回事)的牛的坐标和

ans+=(sum(data[i]-1).num*data[i].position - sum(data[i].position-1).dist + (distance-sum(data[i].position-1).dist - (i-1-sum(data[i]-1).num)*data[i].position ))*data[i].power
可以化简为
int x1=sum(data[i]-1).num,x2=sum(data[i].position-1).dist;
ans+=(data[i].position*(x1*2-i+1) - x2*2 + distance)*data[i].power;
然后distance累加再把当前点add进树状数组就ok了

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