观光公交 贪心证明

· · 个人记录

贪心策略：每次找到能使乘客旅行时间总和减小最多的边加速。

要证明这一点，我们先给出如下定义。

$arrive_i$：公交车到达 $i$ 站点的时刻。 那么离开时间就是两者的最大值。 定义**断点**为 $arrive_i \leq t_i$ 的点。 $n$ 站点也算是断点。每次加速后，从加速的边到第一个断点为止所有的站点 $arrive_i$ 都减去了 $1$。也就是说，以这些点为终点的旅客花费时间都减少了 $1$。 考虑一组最优解 $A$ ,而我们正在构造解 $B$,当前选了一条边 $e$ 加速。若 $e$ 在 $A$ 中加速的次数大于等于我们累计使用的次数，那么显然没问题。如果我们的加速次数超过了 $A$ 中的次数，分两种情况讨论： 1. $A$ 中虽然没有再加速 $e$ ,但加速了 $e$ 到其第一个断点中的**至少**一条边。 考虑这些边，我们发现本来应该在 $e$ 加速后成为断点的点，只是**延迟成为断点**了而已。然而我们用选的 $e$ 替换掉这些边，选的次数不会更多，还能覆盖更大的范围，显然更优。 1. $A$ 中没有再加速 $e$ 到其第一个断点中的**任何**一条边。那么考虑另外一条在 $A$ 中但不在 $B$ 中的边 $e'$ 。由于 $A$ 和 $B$ 在前面的构造**完全相同**，而每加速一条边可能会造成更多断点，因此我们每次选的 $e$ 缩减总时间的量**单调不增**。所以显然，$e'$ 不会比 $e$ 更优。 证毕。