P5914 MOS 题解

· · 题解

一道练习贪心证明的好题。

绝大多数题解只是点出了以下结论：

要么最快的带最慢的；要么最慢的带次慢的。

并没有给出证明。我就补上这个证明。

为了证明这个贪心结论，我们先证明几个引理。

引理一：每次将火把带回来的，一定是对岸最快的。

引理一证明：如果回来的不是对岸最快的，让对岸最快的人代替这个回来的人的一切行动，发现答案至少不差。

引理二：最慢的人要么和最快的人一起过桥，要么和次慢的人一起过桥。

引理二证明：

为了方便表述，记最快的人为 a_1，次快的人为 a_2，以此类推，次慢的人为 a_{n-1}，最慢的人为 a_n。

设 a_n 是与 a_p 一起过桥，a_{n-1} 是与 a_q 一起过桥。

我们有一个调整法的思路：让 a_{n-1} 和 a_n 一起过桥，让 a_p 与 a_q 一起过桥。

显然这样调整后这两次过桥的时间总和变少了。但是现在就得证是错误的。因为我们不确定改变过桥顺序是否会影响其他的过桥。

我们这样调整后唯一可能造成的影响是：如果我们希望 a_p 把火把送回来，那 a_{n-1} 和 a_n 一起过桥就会产生阻碍。

在这种情形下，尝试证明 a_p=a_1 最优。

假设 a_p\ne a_1，我们令 a_p\leftarrow a_1，容易发现，a_n 和 a_p 过桥时间不变，而 a_p 带着火把回来时间至少不变，可能更优。

综上所述，最慢的人每次过桥，要么和最快的人一起，要么和次慢的人一起。

最后的结论：要么 a_1 和 a_n 过桥，a_1 回来；要么 a_1,a_2 先过桥，a_1 回来，然后 a_{n-1},a_n 过桥，a_2 回来。

证明：考虑 a_n 和谁过桥。如果 a_n 和 a_1 过桥，由引理一，过桥后一定是 a_1 回来。

如果 a_n 和 a_{n-1} 过桥，假设是由 a_k 送回火把。因为 a_k 总是有一次过去、一次送回火把、一次回到对岸的过桥旅程，所以 a_k 会贡献至少三次时间至少为 a_k 的过桥。

如果我们先让 a_1,a_2 过桥，a_1 回来，让 a_2 送回 a_n,a_{n-1} 带过去的火把。这种方法贡献了 a_1+2a_2 的时间，a_1+2a_2\le 3a_k，更优。

以上我们证明了这种方法的正确性。如果我还有考虑不周的地方，欢迎评论指出。

代码就不贴了。有了这个结论，每次看一下送走当前 a_n,a_{n-1} 花费更少的是哪种，不停选就是了。

给个关注呗