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

贪心

Posted by angeldust at 2011-12-23 11:05:16 on Problem 1328 and last updated at 2011-12-23 11:05:59
每个岛都在X轴上有一个区间可以被雷达覆盖,x1为可覆盖的左端点,x2为可覆盖的右端点,x1,x2关于岛的X对称。
先对岛以x排序,然后贪心。
假设当前雷达为nowx,如果当前岛的x1<=nowx,那么更新nowx=min(nowx,x2)
否则加一个新雷达,设置nowx=当前岛的x2
总之就是让雷达在满足当前情况的前提下尽量往右方。



另外d和y都是>0的,不用想多了

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