Posted on 2011-01-23 13:20
Onway 阅读(324)
评论(0) 编辑 收藏 引用 所属分类:
伤不起的ACM
题意：在x轴上方，给出n个点的xy坐标，在x轴上安放的一点可以以半径为d产生覆盖，问在x轴上至少要安放几个点才可以将x轴上方的点都覆盖起来。如果不能将全部的点覆盖，那么输出-1。
类型：贪心
思路：如果上方的某个点S能进行覆盖，那么肯定这个点在x轴上能够确定一个范围，在这个范围安放的任何一个点都能将S覆盖。n个点可以产生n个范围，将这些范围的起点按x轴排序从左到右进行排序，注意这些范围中相同起点而不同终点的排法，应该是终点值较大的先排。排完以后，以第一个点的范围开始进行贪心，在这个范围能覆盖的点都放进来，注意更新这个覆盖范围，直到某个点不能进行覆盖为止，这时需要在x轴多安放一点了。
解析得真糟糕。其实就是将二维的覆盖转化为一维的覆盖。
这个题目也想了一个多小时，主要是得到上面的思路比较曲折，自我感觉不太满意。这个题目是转到linxu系统上用vim写的第一个题，也值得纪念一下。用g++编译出来，一个编译错误。提交一次AC，gdb调试都不用，呵呵。