[POJ1328]Radar Installation[贪心]

题面

首先这道题容易想到降维, 一个点P(x, y)能够被圆心O在X轴上的一个圆覆盖, 等价于O在线段[$latex x-\sqrt{r^2-y^2}$, $latex x+\sqrt{r^2-y^2}$]上. 这样就转化为要用最少的点标记所有的区间.

考虑贪心, 根据之前类似区间问题[POJ3190]Stall Reservations[贪心][POJ3614]Sunscreen[贪心]的分析, 我们先把这些区间按左端点排序, 依次考虑每个区间, 把雷达(开始位于pos=-inf)尽量往后放, 放在当前能管到的区间最大的一个右端点处; 如果扫到的区间的左端点都比当前能管到的最大的一个右端点(当前雷达位置pos)还靠右, 就新建一个雷达放在这个区间的右端点, 更新pos.

证明类似于[POJ3190]Stall Reservations[贪心].

注意如果有一个点离X轴太远, 要输出无解.

UPD: 进阶指南上的严谨证明

对于每个区间[a[i].l, a[i].r], 有两种决策: 1 使用已有的点标记它; 2 新建一个点标记它

若选择1, 下一个雷达可以放在任意位置, 但选择2的话必须把一个新的雷达放在区间[a[i].l, a[i].r]内. 决策1的可达状态包含了决策2.

同理, 把雷达尽量往后放这一决策达到的状态, 也包含了放在靠前位置的可达状态.

因此这样的策略不会使后面的决策被制约, 是优秀的.

这种方法叫做 决策包容性.

实际上[POJ3190]Stall Reservations[贪心]也可以这样理解.

赞(0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址