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 |
Re:关于1328的解题思路~~In Reply To:关于1328的解题思路~~ Posted by:loveKid at 2009-04-17 14:45:49 > 该题题意是为了求出能够覆盖所有岛屿的最小雷达数目,而由题目我们可以求出每个岛屿雷达能覆盖的区间,该区间在岛屿横坐标两边对称的长度[x-sqrt(d*d-y*y),x+sqrt(d*d-y*y)];然后我们对岛屿按左区间从小到大排序,说到这里,我们脑海中就浮现出来了贪心的经典活动安排问题,把这些区间看成一个活动的【开始时间--结束时间】,要求我们尽可能地选择一个方案最多的活动,前提是活动要兼容,即时间不冲突,而所求的最多方案是就是我们要求的最小雷达数目;例如这组数据; > 3 2 > 0 0 > 1 2 > 4 0 > 我们可以算出时间区间并排序后有:1【-2,2】2【1,1】,3【2,6】;我们用一个变量currentRight记录当前的右区间,首先currentRight=2;因为区间2的开始区间在区间1的右区间的里面,因此1.2区间有交集,这时候我们不给2增加雷达,1,2交集后,我们要更新因为currentRight=2>区间2的1;所以currentRight=1;对于区间3,因为currentRight=1<2,不想交,因为要增加一个雷达数,所以该组数据为2;即可求解。还没有的兄弟们,加油哦~ > > > PS:题目中数据有出现d<=0,直接输出Case #: -1即可,如果还一直卡住过不了的可以去参考我的代码http://lovekid1987.blog.163.com/blog/static/11518421020093172218978/ Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator