曼哈顿距离中位数选址：从水题到通用解题框架

1. 从一道“水题”说起：为什么它值得认真拆解

“Lunch in Grid City”这个标题，第一次看到的人大概率会愣一下——听起来像是个模拟经营游戏，或者某个城市午餐配送的调度问题。实际上，这是一道出现在算法竞赛训练题单里的经典题目，被很多刷题者归入“水题”类别。所谓水题，通常指思路直白、代码量小、不需要复杂数据结构或高级算法就能解决的题目。但我想说的是，水题恰恰是最值得拿来拆解的素材，因为它把一个核心算法思想压缩到了最简形态，没有多余的干扰项，你能清清楚楚地看到问题本质。

这道题的核心场景是这样的：在一个网格状布局的城市里，有若干栋建筑分布在不同的坐标点上，现在要选一个位置开一家午餐配送中心，使得所有建筑到配送中心的曼哈顿距离之和最小。曼哈顿距离是指两点在网格上沿水平方向和垂直方向移动的距离之和，也就是 |x1 - x2| + |y1 - y2|。这个问题在算法领域有个更通用的名字——曼哈顿距离下的中位数问题，或者叫一维中位数问题的二维推广。

为什么说它“水”？因为一旦你意识到曼哈顿距离的可加性——水平方向的距离和垂直方向的距离是相互独立的——问题就拆成了两个一维问题：在 x 坐标集合中找一个点使得到所有 x 的距离之和最小，在 y 坐标集合中做同样的事。而一维情况下，这个最优点就是中位数。所以整道题的解法就是：把所有建筑的 x 坐标排序取中位数，y 坐标排序取中位数，然后计算总距离。

听起来确实简单。但我在带新人的过程中发现，很多人能背出“取中位数”这个结论，却说不清楚为什么是中位数而不是平均数，也不知道当坐标点数量是偶数时该取哪个值，更不清楚这个结论的适用边界在哪里。这篇文章就是要把这些“水面下的东西”全部捞出来，让你不仅会做这道题，还能理解这一类问题的通用解法，以后遇到变体也能自己推导。

适合阅读这篇文章的人包括：正在刷算法题但不想只背答案的学习者、需要给新人讲解中位数性质的教学者、以及任何对“最优化选址”这类问题感兴趣的开发者。我会从问题建模开始，一步步推导解法，给出可直接运行的代码，最后分享我在实际做题和教学中积累的避坑经验。

2. 问题建模与核心思路拆解

2.1 曼哈顿距离的可加性：把二维问题拆成一维

曼哈顿距离的定义是两点在标准坐标系上的绝对轴距之和。假设配送中心选在坐标 (x, y)，第 i 栋建筑的坐标是 (xi, yi)，那么总距离可以写成：

总距离 = Σ(|xi - x| + |yi - y|) = Σ|xi - x| + Σ|yi - y|

这个等式看起来平平无奇，但它揭示了一个关键性质：x 方向和 y 方向的贡献是完全独立的。也就是说，无论 x 取什么值，都不会影响 y 方向的距离和，反之亦然。这意味着我们可以分别最小化 Σ|xi - x| 和 Σ|yi - y|，两个方向的最优解组合起来就是全局最优解。

这个性质在算法题里非常常见，我习惯把它叫做“维度解耦”。很多二维甚至多维问题，如果距离度量满足可加性，都可以拆成独立的一维问题来解。曼哈顿距离满足这个性质，欧几里得距离就不满足——因为欧氏距离里 x 和 y 的差值是平方和开根号，两个维度耦合在一起，不能简单拆开。所以这道题用曼哈顿距离而不是欧几里得距离，本身就是出题人给的一个“提示”。

注意：维度解耦的前提是距离函数可加。如果题目换成欧几里得距离，中位数解法就失效了，需要用梯度下降或 Weiszfeld 算法迭代求解。看到“曼哈顿距离”或“网格城市”这类关键词时，优先考虑中位数思路。

2.2 一维中位数的最优性证明：为什么不是平均数

现在问题简化成：给定一组数 a1, a2, ..., an，找一个实数 x，使得 f(x) = Σ|ai - x| 最小。这个函数是凸函数，因为绝对值函数是凸的，凸函数的和仍然是凸函数。凸函数的最小值出现在导数为零的点，或者更准确地说，出现在次梯度包含零的点。

对 f(x) 求次梯度：每个 |ai - x| 的次梯度在 x ≠ ai 时是 sign(x - ai)，在 x = ai 时是区间 [-1, 1]。所以 f(x) 的次梯度是 Σ sign(x - ai)（在不可导点需要特殊处理）。当 x 小于所有 ai 时，所有 sign 都是 -1，次梯度为 -n；当 x 大于所有 ai 时，次梯度为 +n。随着 x 从负无穷移动到正无穷，次梯度从 -n 逐步增加到 +n，每次经过一个 ai 就增加 2。次梯度包含零的位置，恰好是使得 x 左右两侧数据点数量尽可能均衡的位置——也就是中位数。

换个更直观的说法：假设你站在数轴上的某个位置 x，左边有 L 个点，右边有 R 个点。如果你往右移动一小步，左边所有点到你的距离各增加一点点，右边所有点到你的距离各减少一点点。净变化是 L - R 乘以步长。如果 L > R，往右移动会让总距离增加，说明应该往左走；如果 L < R，往右移动会让总距离减少，说明应该往右走；只有当 L = R 或者左右差距不超过 1 时，你才处于最优位置。这正是中位数的定义。

而平均数呢？平均数最小化的是平方误差和 Σ(ai - x)²，不是绝对误差和。这两个目标函数的最优解一般不同。举个简单例子：数据是 [1, 2, 100]。中位数是 2，总绝对距离是 |1-2| + |2-2| + |100-2| = 1 + 0 + 98 = 99。平均数是 34.33，总绝对距离是 33.33 + 32.33 + 65.67 = 131.33。中位数明显更优。原因就是平均数会被极端值拉偏，而中位数对极端值稳健。

2.3 偶数个点的处理：取中间两个之间的任意值

当 n 是偶数时，中位数不唯一。比如数据 [1, 2, 3, 4]，取 x = 2 时总距离是 1 + 0 + 1 + 2 = 4；取 x = 3 时总距离是 2 + 1 + 0 + 1 = 4；取 x = 2.5 时总距离是 1.5 + 0.5 + 0.5 + 1.5 = 4。事实上，x 取 [2, 3] 区间内任意值时，总距离都是 4。这是因为当 x 在中间两个数之间时，左边有两个点右边有两个点，L = R = 2，往左往右移动的净变化都是零。

对于这道题来说，如果建筑数量是偶数，取中间两个坐标中的任意一个（或者它们之间的任意值）都能得到相同的最小总距离。实际编码时通常取排序后下标为 n/2 的元素（下取整），或者取 (n-1)/2 和 n/2 两个位置分别计算取较小值。两种方式结果一样，因为总距离相同。

实操心得：我在写这道题时习惯直接取排序后第 n/2 个元素（0-indexed），不管 n 是奇数还是偶数。对于偶数情况，这个位置是中间偏右的那个数，它和中间偏左的数给出的总距离是一样的。这样代码最简洁，不需要特判。

3. 完整实操流程与代码实现

3.1 输入解析与数据组织

这道题的输入格式通常是：第一行给出测试用例数量 T，每个测试用例第一行给出建筑数量 n，接下来 n 行每行两个整数表示建筑坐标。有些版本还会给出网格的边界尺寸，但那些信息对解题没有影响，因为最优位置一定在建筑坐标的范围内，不会跑到边界外面去。

我一般用两个列表分别存 x 坐标和 y 坐标，因为后续要对它们分别排序。用 Python 写的话大概是这样：

t = int(input()) for _ in range(t): n = int(input()) xs = [] ys = [] for _ in range(n): x, y = map(int, input().split()) xs.append(x) ys.append(y) # 后续处理

这里有个细节：有些题目的输入里 n 后面可能跟一个多余的空行，或者坐标之间有多余空格。用split()和map()组合能自动处理这些情况，不需要额外清洗。但如果输入格式特别不规范，比如坐标用逗号分隔，那就需要手动替换分隔符。我在实际做题时遇到过用制表符分隔的版本，split()默认按任意空白字符分割，所以也能正确处理。

3.2 排序与中位数选取

拿到 xs 和 ys 之后，分别排序，然后取中位数：

xs.sort() ys.sort() mid_x = xs[n // 2] mid_y = ys[n // 2]

这里 n // 2 是整数除法，对于 n = 5 得到 2，对应排序后第三个元素（0-indexed），正好是中位数。对于 n = 4 得到 2，对应排序后第三个元素，是中间偏右的那个。前面说过，偶数情况下取哪个都行，总距离一样。

注意：不要用n / 2然后取整，因为浮点数除法在 Python 里得到的是 float，不能直接当索引。用//整除运算符最稳妥。其他语言里也要注意整数除法的问题，比如 C++ 里n / 2对正整数就是整除，Java 里也是，但 JavaScript 里n / 2可能得到小数，需要用Math.floor(n / 2)。

3.3 总距离计算与输出

有了中位数坐标之后，遍历所有建筑计算曼哈顿距离之和：

total = 0 for i in range(n): total += abs(xs[i] - mid_x) + abs(ys[i] - mid_y) print(total)

这里可以直接用排序后的 xs 和 ys，因为排序不改变元素集合，只是改变了顺序。用原始未排序的列表也一样，但既然已经排序了，直接用排序后的列表更省事。

完整代码合并起来：

t = int(input()) for _ in range(t): n = int(input()) xs = [] ys = [] for _ in range(n): x, y = map(int, input().split()) xs.append(x) ys.append(y) xs.sort() ys.sort() mid_x = xs[n // 2] mid_y = ys[n // 2] total = sum(abs(x - mid_x) + abs(y - mid_y) for x, y in zip(xs, ys)) print(total)

这段代码的时间复杂度是 O(n log n)，主要花在排序上。对于 n 达到 10^5 级别的输入也能轻松跑完。空间复杂度是 O(n)，用来存坐标。

3.4 参数选择与边界情况处理

虽然这道题本身很简单，但有几个边界情况值得注意：

• n = 1 时，中位数就是唯一的那个点，总距离为 0。代码里 n // 2 = 0，取第一个元素，正确。
• 坐标有负数时，排序和绝对值计算都不受影响。Python 的abs()对负数正常工作。
• 坐标值很大时，比如达到 10^9，总距离可能超过 32 位整数范围。Python 自动处理大整数，但用 C++ 或 Java 的话需要用long long或long。我一般估算一下：n 个点，每个距离最大 2 * 10^9，总和最大 2 * 10^14，确实超出 int 范围。
• 多个测试用例之间，xs 和 ys 要重新初始化，不能复用上一个用例的数据。用循环内新建列表的方式最安全。

踩过的坑：有一次我为了省事，把 xs 和 ys 定义在循环外面，每次用clear()清空。结果某个测试用例的输入读取出了问题，导致列表里残留了上一个用例的数据，答案错了但看不出来。后来改成循环内新建列表，问题消失。这种“省事”的写法在竞赛中风险很高，不建议。

4. 常见问题与排查技巧实录

4.1 为什么我的答案和标准答案差了一点

这是最常见的问题。通常有几个原因：

第一，中位数取错了。有些人取的是(n-1) // 2，对于奇数 n 这是对的，对于偶数 n 取的是中间偏左的数。虽然总距离和中间偏右一样，但如果题目要求输出具体的配送中心坐标，那就会和标准答案不同。不过这道题通常只要求输出最小总距离，所以取哪个都行。如果题目要求输出坐标，需要看清楚题目对偶数情况的约定。

第二，距离计算时用了欧几里得距离。有些人看到“城市”“网格”就下意识用了平方和开根号，但题目明确说的是曼哈顿距离。曼哈顿距离是横平竖直走，欧几里得距离是直线飞过去，两者完全不同。

第三，整数溢出。前面提到过，坐标值大、点数多的时候总距离可能超出 int 范围。用 Python 不会遇到这个问题，但用其他语言要注意。

第四，输入读取不完整。有些题目的输入里，n 后面可能跟了额外的数字（比如网格尺寸），如果只读 n 个坐标就结束，后面的数字会残留到下一个测试用例的读取中，导致连锁错误。我一般会仔细看题目描述的输入格式，确认每个测试用例到底有多少行、每行几个数。

4.2 中位数和平均数的选择困惑

很多人会问：为什么不用平均数？平均数不是更“公平”吗？这个问题我在前面已经从数学上解释过了，这里再给一个生活化的类比。

假设你和两个朋友约在某个地点见面。你住在位置 1，朋友 A 住在位置 2，朋友 B 住在位置 100。如果选平均数 34.33 作为见面地点，你走 33.33，A 走 32.33，B 走 65.67，总距离 131.33。如果选中位数 2 作为见面地点，你走 1，A 走 0，B 走 98，总距离 99。虽然后者让 B 走得更远，但总距离更小。中位数的逻辑是“少数服从多数”——它让大多数人的距离尽可能小，代价是极端位置的人走得更远。平均数则试图让每个人都“平均分担”，但结果反而是总距离更大。

在实际应用中，如果目标是总距离最小，中位数是最优解。如果目标是最大距离最小（让最远的人尽量近），那是另一个问题，解法是找最小覆盖圆或最小包围盒，不是中位数。

4.3 多维情况的扩展思路

如果题目从二维扩展到三维甚至更高维，曼哈顿距离的可加性依然成立，每个维度独立取中位数即可。比如三维空间中有 n 个点 (xi, yi, zi)，最优配送中心是 (median(x), median(y), median(z))。证明方法和二维完全一样，因为曼哈顿距离在每一维上的贡献是独立的。

但如果距离度量换成欧几里得距离，问题就复杂了。二维欧几里得距离下的最小距离和问题没有闭式解，需要用迭代方法。这也是为什么算法竞赛里曼哈顿距离的题目远多于欧几里得距离——前者有漂亮的中位数解法，后者只能数值求解。

4.4 常见问题速查表

独家避坑技巧：我习惯在本地测试时加一个暴力验证函数。对于小规模输入（n ≤ 10），枚举所有可能的配送中心位置（在建筑坐标范围内），计算总距离，取最小值。然后和我的中位数解法对比。如果两者一致，说明解法正确。这个方法在遇到新题时特别有用，能快速验证思路是否正确，比盯着代码看半天高效得多。

5. 从这道题延伸出的通用解题框架

5.1 最优化选址问题的分类与识别

“Lunch in Grid City”本质上是一个最优化选址问题。这类问题的通用形式是：给定一组需求点，选择一个设施位置，使得某个目标函数最优。目标函数不同，解法完全不同。我整理了一个分类表：

看到题目时，先识别距离度量和目标函数，然后查表找对应解法。这道题是“曼哈顿距离 + 距离和最小”，对应“各维中位数”，所以解法就是排序取中位数。

5.2 中位数性质的更多应用场景

中位数最小化绝对距离和这个性质，在实际工程中也有很多应用。比如物流仓库选址：假设你要建一个仓库给多个门店供货，门店分布在城市的不同位置，货车只能沿街道行驶（曼哈顿距离），那么仓库建在门店坐标的中位数位置，总运输距离最小。再比如数据中心选址：多个客户端需要连接到一个服务器，网络延迟近似正比于曼哈顿距离，服务器放在客户端坐标的中位数位置，总延迟最小。

这些场景的共同点是：距离度量可加、目标是最小化总距离、没有其他约束（比如容量限制、地形障碍）。一旦加入约束，问题就变成约束优化，可能需要线性规划或启发式算法。但在无约束的理想情况下，中位数就是最优解。

5.3 代码模板与复用建议

我把这道题的解法整理成一个通用模板，以后遇到类似问题可以直接套用：

def min_manhattan_sum(points): """ 给定一组二维点，返回曼哈顿距离和的最小值。 points: List[Tuple[int, int]] """ if not points: return 0 xs = sorted(p[0] for p in points) ys = sorted(p[1] for p in points) n = len(points) mid_x = xs[n // 2] mid_y = ys[n // 2] return sum(abs(x - mid_x) + abs(y - mid_y) for x, y in points)

这个模板可以直接用于任何“曼哈顿距离和最小”的问题，只需要把输入点传进去即可。如果题目要求返回最优位置而不是最小距离，把mid_x和mid_y返回就行。

实操心得：我在刷题时习惯把每道题的解法抽象成一个函数，存到自己的代码库里。下次遇到类似题目，先搜代码库，找到可复用的部分，再根据题目具体要求调整。这样比每次从零开始写快得多，而且能避免重复踩坑。这道题的中位数模板我已经用过至少五次，每次都是微调输入输出格式就搞定了。

5.4 复杂度分析与优化空间

当前解法的时间复杂度是 O(n log n)，瓶颈在排序。能不能优化到 O(n)？理论上可以，因为找中位数不需要完全排序，用快速选择算法（Quickselect）可以在平均 O(n) 时间内找到第 k 小的元素。C++ 的nth_element就是干这个的，Python 没有内置的快速选择，但可以用heapq.nsmallest或者自己实现。

不过对于这道题来说，O(n log n) 完全够用。竞赛题的时间限制通常允许 n 达到 10^5 甚至 10^6，排序的开销完全可以接受。除非 n 达到 10^7 级别，否则没必要为了 O(n) 去写复杂的快速选择。我在实际做题时，除非题目明确卡时间复杂度，否则优先选最简单的排序解法，因为代码短、不易出错。

空间复杂度方面，我们需要存所有坐标，所以是 O(n)。如果输入数据特别大，可以考虑流式读取，但中位数需要知道所有数据才能确定，所以没法做到 O(1) 空间。这是问题本身的性质决定的，不是算法的问题。

6. 我在教学和实战中积累的经验

带新人做这道题时，我发现一个有趣的现象：很多人能很快写出代码并通过样例，但当我问“为什么中位数是最优的”时，他们答不上来。这说明他们只是记住了结论，没有理解原理。而理解原理的好处是，遇到变体时能自己推导，而不是干瞪眼。

比如有一次我出了一道变体题：配送中心只能建在已有的建筑位置上，不能建在任意坐标。这时候中位数解法还适用吗？答案是：如果中位数位置恰好有建筑，那没问题；如果没有，就需要在建筑位置中找最接近中位数的那个。因为目标函数是凸函数，在离散候选点中，最优点一定在连续最优点的附近。具体来说，排序后取第 n//2 个建筑的位置作为配送中心即可，因为那个位置就是“离散中位数”。

再比如另一道变体：每个建筑有一个权重，表示配送需求量，目标是最小化加权距离和。这时候需要找加权中位数——使得左侧权重和不超过总权重一半、右侧权重和也不超过总权重一半的位置。解法是先按坐标排序，然后累加权重，找到第一个使累加权重超过总权重一半的位置。这个思路和普通中位数一脉相承，只是从“数个数”变成了“数权重”。

这些变体在面试和竞赛中都很常见。如果你只背了“取中位数”这个结论，遇到加权版本就懵了；但如果你理解了“中位数使得左右两侧均衡”这个本质，加权版本就是自然的推广。

最后分享一个我常用的调试技巧：对于小规模输入，我会手动枚举所有可能的配送中心位置，打印每个位置的总距离，然后观察最小值出现在哪里。这个方法能直观地验证中位数结论，也能帮助理解为什么平均数不是最优的。我试过用 [1, 2, 100] 这组数据，枚举从 1 到 100 的所有整数位置，打印总距离曲线，可以看到曲线在 2 附近最低，然后向两侧上升，在 100 附近又有一个局部高点。这个可视化过程比看数学证明更有说服力。

这道题虽然被归为“水题”，但它承载的算法思想——维度解耦、凸函数最优性、中位数性质——是很多高级算法的基础。把它吃透，比刷十道同类型的题更有价值。