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 |
贪心每个岛都在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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator