[APIO2012]守卫-provement

Deu5ExMach1na · 2021-12-11 15:46:58 · 题解

既然题解区和网上都没人发贪心的证明，那我姑且就写一篇吧。

0. 题意转换：

给定一些闭区间：

求最少添加多少个点能让所有区间内至少有一个点。

即最少点区间覆盖（瞎编的名字）。

1. 初步分析：

发现若大区间内包含一个小区间，则可以将大区间删去。

（因为小区间内必定有点，所以也满足了大区间的约束，又因为要用最少的点，所以大区间的其他地方不需要添加点）

在删去了所有的大区间后：若我们把所有区间按左端点排序，显然，右端点也是递增的。（不然必会有包含关系）

2. 再度分析：

如图：这是我们排好序的区间：

假设我们在区间 I_4 处的某一个点放置一个点，它使得 I_1，I_2，I_3，I_4 内都有了一个点，那么可以轻易推导，我们在 I_1 的最右端放一个点，它的效果和在 I_4 处某个地方放一个的点是等效的。

这意味着任何一个放置方案都可以转化为只在一些区间的右端放一些点，包括最优方案。

所以我们只用找在区间右端点放点的最优方案。

3. 再再度分析：

假设我们在 I_j 的右端点处放了一个点，它使 I_j 至 I_a 的区间满足了需求，而若在 I_{j-1} 处放一个点，它使 I_{j-1} 至 I_b 的区间满足了需求，则 b 一定小于 a。

换成人话，若在上一个区间放点，它的作用效果必定减小。

这说明：最优的放点方案，任意相邻的两个点，后一个点一定紧接在前一个点的有效范围后面，不会在里面。

于是，这便得到了贪心的放点方案：

从 1 扫到 n，必须放就放在最右端，不用放点就跳过。