自动搬运

查看原文

来自洛谷，原作者为

	Daniel13265 **

搬运于2025-08-24 21:33:21，当前版本为作者最后更新于2022-02-21 15:23:55，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

本文仅用于补充其他题解。其他题解未详细说明结论「存在至少一组最优方案使得每个交叉路口海拔都为 $0$ 或 $1$，且海拔都为 $0$ 和 $1$ 的交叉路口分别仅构成一个极大四连通块」，本文予以简要证明。本文由讨论中单独提出，应@yurzhang 要求提交为题解（详见原讨论此题题解存在共同问题）。

下文「连通块」指「内部点高度相同的极大四连通块」。

对于一个方案，若存在高度小于 $0$ 的点，则令所有这些点的高度为 $0$ 更优，因为这些点之间的贡献减小为 $0$，而其他点的高度无论在调整前后都大于等于这些点的，所以这些点与其他点的贡献一定减小了。同理若存在高度大于 $1$ 的点，则令所有这些点的高度为 $1$ 更优。

现在每个点高度在 $[0,1]$ 区间内，假设其不全为 $0$ 或 $1$。对于所有不包含西北角的连通块，找到高度最小的一个（称为 $S$），这个连通块一定存在且不包含东南角。

• 若 $S$ 不与西北角所在的连通块相邻，则将其高度调整为与其相邻的点中的最小高度一定更优，因为 $S$ 内点之间的贡献不变为 $0$，而相邻点的高度无论在调整前后都大于等于这些点的，所以 $S$ 内的点与其相邻点的贡献一定减小了。
• 若 $S$ 与西北角所在的连通块相邻，则找到与之相邻的点中高度不为 $0$ 且最小的（假设高度为 $h$），$S$ 的高度一定在 $0$ 与 $h$ 之间。如果将 $S$ 的高度看作自变量 $x\in[0,h]$，那么令 $x=0$ 或 $x=h$ 一定不更劣，因为 $S$ 内点之间的贡献不变为 $0$，而 $S$ 内的点与其相邻点的贡献是线性函数，最小值一定能在两端取到。

无论是哪种情况，都存在一种不更劣的、连通块更少的方案。不断进行调整，最终每个点的高度一定会停于 $0$ 或 $1$。从而，一定存在一组最优方案使得点的高度都为 $0$ 或 $1$。