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

Re:关于1328的解题思路~~

Posted by sdie2008140224 at 2010-03-30 19:55:45 on Problem 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:
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