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

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.33A 走 32.33B 走 65.67总距离 131.33。如果选中位数 2 作为见面地点你走 1A 走 0B 走 98总距离 99。虽然后者让 B 走得更远但总距离更小。中位数的逻辑是“少数服从多数”——它让大多数人的距离尽可能小代价是极端位置的人走得更远。平均数则试图让每个人都“平均分担”但结果反而是总距离更大。在实际应用中如果目标是总距离最小中位数是最优解。如果目标是最大距离最小让最远的人尽量近那是另一个问题解法是找最小覆盖圆或最小包围盒不是中位数。4.3 多维情况的扩展思路如果题目从二维扩展到三维甚至更高维曼哈顿距离的可加性依然成立每个维度独立取中位数即可。比如三维空间中有 n 个点 (xi, yi, zi)最优配送中心是 (median(x), median(y), median(z))。证明方法和二维完全一样因为曼哈顿距离在每一维上的贡献是独立的。但如果距离度量换成欧几里得距离问题就复杂了。二维欧几里得距离下的最小距离和问题没有闭式解需要用迭代方法。这也是为什么算法竞赛里曼哈顿距离的题目远多于欧几里得距离——前者有漂亮的中位数解法后者只能数值求解。4.4 常见问题速查表问题现象可能原因排查方法解决方案答案偏大用了欧几里得距离检查距离公式改用曼哈顿距离答案偏小中位数取错位置打印排序后的数组和中位数确认取 n//2 位置部分用例答案错误整数溢出检查变量类型改用 long long 或 Python所有用例答案错误输入读取格式不对打印读到的数据按题目格式重新解析偶数个点时答案不稳定中位数不唯一验证两个中间值取任意一个均可总距离相同多测试用例结果串了列表未清空检查列表初始化位置每个用例新建列表独家避坑技巧我习惯在本地测试时加一个暴力验证函数。对于小规模输入n ≤ 10枚举所有可能的配送中心位置在建筑坐标范围内计算总距离取最小值。然后和我的中位数解法对比。如果两者一致说明解法正确。这个方法在遇到新题时特别有用能快速验证思路是否正确比盯着代码看半天高效得多。5. 从这道题延伸出的通用解题框架5.1 最优化选址问题的分类与识别“Lunch in Grid City”本质上是一个最优化选址问题。这类问题的通用形式是给定一组需求点选择一个设施位置使得某个目标函数最优。目标函数不同解法完全不同。我整理了一个分类表距离度量目标函数最优解位置典型算法曼哈顿距离距离和最小各维中位数排序取中位数曼哈顿距离最大距离最小最小包围盒中心扫描线或二分欧几里得距离距离和最小无闭式解Weiszfeld 迭代欧几里得距离最大距离最小最小覆盖圆圆心随机增量算法曼哈顿距离距离平方和最小各维平均数直接计算看到题目时先识别距离度量和目标函数然后查表找对应解法。这道题是“曼哈顿距离 距离和最小”对应“各维中位数”所以解法就是排序取中位数。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 附近又有一个局部高点。这个可视化过程比看数学证明更有说服力。这道题虽然被归为“水题”但它承载的算法思想——维度解耦、凸函数最优性、中位数性质——是很多高级算法的基础。把它吃透比刷十道同类型的题更有价值。