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

多次失败后,AC了,发解题报告,应该是比较详细的。树状数组做的

Posted by AllenLSY at 2010-08-27 19:25:27 on Problem 1990
http://allenlsy.com/2010/08/27/poj-1990/

题意:牛的听力为v,两头牛i,j之间交流,需要max(v[i], v[j])*dist(i,j)的音量。应该说,题意是说,v[i]越小,听力越好。
求所有牛交谈时叫声总和∑(max(v[i],v[j])*abs(dist[j]-dist[i]) ) )
思路:先对牛按照v从小到大排序。对于牛i,它与比他听力还小的牛之间交谈需要音量都是v[i],再乘以之间的距离就可以了。在排好序后,假设:
count[i]:比i听力小的且x坐标比第i头牛小的牛总数
total[i]:count[i]中那些牛的x坐标总和
alltotal:表示所有比第i头牛听力小的牛的总数的话
那么,原题要求的式子就成了
∑( v[i] * 所有比i听力小的牛到i的总距离 )
=∑( v[i] * (count[i]*x[i] – total + alltotal – total – (i – count[i] – 1) * x[i] ) )
其中,count[i]*x[i] – total表示所有比i听力小且在它左边的牛们到i的距离总和, alltotal – total – (i – count[i] – 1) * x[i] ) 表示所有比i听力小且在它右边的牛们到i的距离总和。这个有点难理解,自己画个图试试看。
剩下的关键就在,如何求count[i]和total[i]更快。因为如果排好序后是扫一遍所有牛的坐标的话,时间复杂度就是n^2了,不行。所以想到了树状数组。树状数组用于动态的求一个数组前i个数的总和。
所以,把count作为一个树状数组,如果在坐标x上有一头牛,那么count[x] = 1。这样求i之前有多少头牛,就是count(i)的一个查询。把total同样作为一个树状数组,如果坐标x上有一头牛,那么total[x] = x。这是因为total数组表示的是距离。这样求i之前听力小于v[i]且在i左边的牛总数,就是total(i)的查询。

WA了好几次,发现应该把树状数组里面的查询函数返回值也设成long的才行。冤死了。

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