自动搬运

查看原文

来自洛谷，原作者为

	Wilderness_ AFOed，偶尔会再来

搬运于2025-08-24 21:38:09，当前版本为作者最后更新于2025-01-24 09:21:16，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

我们充分发扬人类智慧。

题目要求的式子是 $\min\limits_{1\le i\le n}(\max\limits_{1\le j\le n}dis(p_i,p_j)-\min\limits_{1\le j\le n}dis(p_i,p_j))$，其中 $dis(a,b)$ 是 $a,b$ 两点间的曼哈顿距离。

我们先将求固定一点的两点间最大曼哈顿的式子 $\max\limits_{1\le j\le n}dis(p_i,p_j)$ 转化一下。

展开 $dis(a,b)$，得

$$\max\limits_{1\le j\le n}|p_{i_x}-p_{j_x}|+|p_{i_y}-p_{j_y}| $$

拆开绝对值，得

$$\max\limits_{1\le j\le n}(\max\{(p_{i_x}+p_{i_y})−(p_{j_x}+p_{j_y}),(p_{i_x}-p_{i_y})−(p_{j_x}-p_{j_y}),(-p_{i_x}+p_{i_y})−(-p_{j_x}+p_{j_y}),(-p_{i_x}-p_{i_y})−(-p_{j_x}-p_{j_y})\}) $$

根据 $\max$ 的性质，得

$$\max\{(p_{i_x}+p_{i_y})-\min\limits_{1\le j\le n}(p_{j_x}+p_{j_y}),(p_{i_x}-p_{i_y})-\min\limits_{1\le j\le n}(p_{j_x}-p_{j_y}),(-p_{i_x}+p_{i_y})-\min\limits_{1\le j\le n}(-p_{j_x}+p_{j_y}),(-p_{i_x}-p_{i_y})-\min\limits_{1\le j\le n}(-p_{j_x}-p_{j_y})\} $$

显然，我们可以 $O(n)$ 预处理求出四个 $\min$ 中的式子，那么查固定一点的两点间最大曼哈顿距离可以 $O(1)$ 实现。

求固定一点的两点间最小曼哈顿距离就可以将点按横坐标升序排序。

根据数学直觉，最小距离中的另一个点在数组中肯定不会离那个固定的点太远，所以我们取固定的点的前 $500$ 个点和后 $500$ 个点枚举即可。

这样速度快得飞起，总时间只花了 $670ms$ 左右，足以通过此题。