这道题出自《算法竞赛进阶指南》0x05排序章节原题是AcWing 104货仓选址题目很短但背后藏着一个很有意思的贪心模型。很多初学者第一次见到它第一反应是“货仓选址是不是得用动态规划或者三分”结果一看题解好家伙排序之后取中位数就结束了。今天我把这道题从读题到证明到代码到踩坑整个捋一遍包括为什么是中位数、偶数情况怎么选、代码写long long的原因、以及它和带权中位数、二维曼哈顿选址这类扩展问题之间的关系。如果你正在刷竞赛入门题或者刚学完排序想找点“排序不只是排个序”的感觉这篇应该能帮到你。1. 先说结论货仓选址到底在考什么1.1 一句话还原题目别被“选址”两个字吓到题目描述非常简短数轴上有N家商店坐标分别是A[1]到A[N]现在要在数轴上选一个位置建货仓使得货仓到所有商店的距离之和最小输出这个最小距离和。注意这里的“数轴”就是一维直线不是二维地图。很多同学第一次看到“选址”可能会脑补成平面几何、曼哈顿距离、甚至最短路径其实都不是。它就是一个纯粹的数学最优化问题给定N个点找一个点x让 |x - A1| |x - A2| ... |x - An| 最小。这个式子里只有绝对值加法没有任何复杂限制。所以它考察的本质是两个东西排序以及一个非常经典的贪心结论——中位数。排序在这里承担的角色是“把无序坐标变成有序序列”有了有序序列才能让中位数的性质自然浮现出来。这也是为什么《算法竞赛进阶指南》把它放在排序这一章而不是数学或贪心章节的原因表面上是在排序实际上是利用排序为后续的贪心决策做准备。1.2 为什么答案就是中位数而不是平均数先给结论把所有A[i]从小到大排序取中位数作为货仓位置距离和最小。如果N是奇数中位数唯一如果N是偶数中间两个数之间的任意一个位置都可以距离和一样。这个结论很多同学能背下来但心里没底因为直觉上会觉得“平均数是不是更好”。我举一个反例就明白了商店坐标是1、2、100。平均数约34.3距离和是 |34.3-1| |34.3-2| |34.3-100| ≈ 33.3 32.3 65.7 ≈ 131.3。但取中位数2距离和是 |2-1| |2-2| |2-100| 1 0 98 99。明显中位数更小。为什么平均数不行因为距离函数是绝对值的和不是平方和。平均值最小化的是平方误差中位数最小化的是绝对误差。两者有本质区别平方误差会把离群点放大所以平均数会被极端值“拉过去”而绝对误差对离群点的惩罚是线性的所以不会被极端值绑架。这个差异在数据分布偏斜时非常明显。所以在“距离和”这种衡量方式下中位数是天然的最优解。2. 从读题到算法排序在这里的真正角色2.1 排序是手段不是目的拿到题之后先想想不排序行不行。如果不排序N个点乱序摆在数轴上我们很难直接看出哪个位置是“中间”的。但一旦排序问题立刻变成“在有序序列里找一个位置使得到所有点的距离和最小”这时候就可以用数学方法直接推导。严格证明可以这样想先把排序后的商店坐标记作a1 a2 ... an。假设货仓选在x。我们只看最外面的两个商店a1和an如果x a1那么货仓到a1和an的距离之和是 (a1 - x) (an - x) a1 an - 2x显然x越大这个和越小所以x不应该小于a1。同理x如果大于an也应该往回收。所以最优x一定落在[a1, an]区间内。在这个区间内a1和an这一对点对答案的贡献是(an - a1)这是一个常数不受x影响。于是问题缩小为在剩下的a2到a(n-1)这N-2个点里选x使得到它们的距离和最小。依此类推每次剥掉最外面一对最优x都落在被剥掉区间之内。最后如果N是奇数会剩下正中间那一个点x只能等于它如果N是偶数会剩下中间两个点x在它们之间任意位置都行。这个剥皮式的证明非常直观也解释了为什么答案是中位数。2.2 中位数的两种取法怎么实现最省事具体实现时有一个小坑中位数到底取哪个下标。假设数组是0-indexed排序后长度为n。当n是奇数比如n5中位数是a[2]。当n是偶数比如n4中位数理论上可以是a[1]到a[2]之间的任何值代码里习惯上取a[2]即a[n/2]或者a[1]即a[(n-1)/2]都行因为距离和一样。很多题解写 ans abs(a[i] - a[n/2])也就是统一取排序后下标为n/2的元素。为什么不是a[(n-1)/2]其实两种写法在这个题里答案完全相同。但取a[n/2]有个好处当n为奇数时n/2就是正中间那个规范当n为偶数时n/2是中间偏右那个虽然和中间偏左那个计算结果一样但代码更统一。实际用哪个都无所谓关键是计算距离和时所有商店都用同一个mid做差不能一会儿用a[n/2]一会儿用a[(n-1)/2]。另外有人会问偶数情况是不是选中间两个数之内的任意点都行是的。比如商店在0和10货仓设在5距离和是10设在3距离和也是10设在-1距离和是12就不行了。因为中间两个端点之间的区间内一对最外点的贡献恒为(an - a1)不会多也不会少。但代码实现时我们只需要输出距离和所以选哪个中位数其实无所谓只要计算正确答案就正确。3. 完整实现与细节处理3.1 C标准写法新手照着抄就行直接给出最常规的写法#include bits/stdc.h using namespace std; int main() { int n; cin n; vectorlong long a(n); for (int i 0; i n; i) cin a[i]; sort(a.begin(), a.end()); long long mid a[n / 2]; long long ans 0; for (int i 0; i n; i) { ans llabs(a[i] - mid); } cout ans endl; return 0; }核心就三行排序、取中位数、累加绝对值。这里有几个细节值得展开说。第一为什么要用vectorlong long而不是vectorint。题目的坐标范围在不同OJ上不一样有的坐标给到1e9N给到1e5那么最大距离和大约是1e14级别已经超过int的2.1e9上限所以必须用long long。如果不注意直接在int下累加大数据的测试点一定会WA。第二llabs是long long版本的绝对值。直接用abs在某些编译器下可能被当作int处理虽然很多情况下能隐式转换但严谨一点还是用llabs。或者你也可以写a[i] mid ? a[i] - mid : mid - a[i]效果一样。第三排序用sort就够了。N最大也就是1e5左右O(N log N)的排序完全没问题没必要上什么复杂度更低的算法。在竞赛中简洁和正确永远是第一位的。3.2 不排序的进阶写法nth_element到底怎么回事如果你已经把这道题刷得很熟或者遇到N特别大、O(N log N)被卡的情况可以考虑用nth_element来找中位数它的平均复杂度是O(N)。#include bits/stdc.h using namespace std; int main() { int n; cin n; vectorlong long a(n); for (int i 0; i n; i) cin a[i]; nth_element(a.begin(), a.begin() n / 2, a.end()); long long mid a[n / 2]; long long ans 0; for (int i 0; i n; i) { ans llabs(a[i] - mid); } cout ans endl; return 0; }nth_element的作用是把数组重新排列使得第n/2个位置从0开始的元素正好是“序列按升序排序后该位置应该有的元素”并且它左边的元素都不大于它右边的元素都不小于它。但它不会完全排序整个数组所以O(N)的平均复杂度。要注意的是nth_element是一个部分排序算法它会改变数组内容而且不保证左右两边各自有序。如果你后面还需要整个数组有序就不要用它。另外它在C标准库里的实现平均很快但并不是严格意义上的“保证O(N)”最坏情况下也可能退化为O(N^2)只是实际竞赛中很少遇到。从学习角度讲我建议先把sort版写好、完全理解了再玩nth_element。因为这道题核心是中位数性质而不是选择算法本身。直接用sort最稳等以后遇到类似“动态中位数”“对顶堆”这类问题再慢慢接触更高级的数据结构。3.3 边界条件和多组输入处理这道题的边界条件比想象中多新手容易在这里丢分。第一只有一个商店。n1时中位数就是a[0]距离和是0代码天然正确不用特判。第二多个测试用例。有些OJ版本会说“有多组数据每组第一行一个整数N”此时你需要写成while (cin n)或while (scanf(%d, n) ! EOF)不要只读一次。我见过不少同学把while写成if然后样例过了交上去只有第一组对后面全WA。第三坐标是否包含负数。距离和涉及绝对值负数不影响处理llabs(a[i] - mid)会正确给出非负值。但如果你为了省事写了abs(a[i] - mid)且坐标差超过int范围同样会溢出所以还是老实long long。第四1-indexed和0-indexed容易混淆。如果你用for (int i 1; i n; i)读入中位数下标就是a[(n 1) / 2]取上整或者统一a[n / 2 1]。不要读入用1计算用0写出来乱成一团。我个人的建议是全程0-indexed代码最干净。4. 常见问题与排查技巧实录4.1 “我用的平均数为什么样例过了但提交不过”这是最经典的错法之一。原因前面已经讲过平均数和绝对距离和根本不对应。有的同学可能在小数据上碰巧平均数和中位数一样比如对称分布的数据1、2、3平均数是2中位数也是2距离和都是4样例过了就以为算法对。但一旦数据变成1、2、100立刻露馅。如果你怀疑自己是不是想错了最快的验证方式是暴力枚举把所有可能的货仓位置比如商店坐标的最小值到最大值之间的每个整数都算一次距离和看哪个最小。拿暴力代码和你的贪心代码对拍一旦出差异马上就能定位问题。尤其是刚学贪心的时候对拍是训练直觉的好工具不要觉得麻烦。4.2 “偶数个商店时我的答案和题解不一样”先说结论如果题解输出的是最小距离和那么无论选中位数偏左还是偏右距离和都是一样的不可能不一样。如果不一样大概率是你计算距离和时“混搭”了。举个例子商店坐标1、3、7、9。如果货仓选在3距离和是 |1-3| |3-3| |7-3| |9-3| 2 0 4 6 12。如果选在7距离和是6 4 0 2 12。如果选在5距离和是4 2 2 4 12。确实一样。偶数情况最优值是一个常数任何位于中间两个数之间的位置都可以。那为什么你算出来不一样很可能是你把货仓位置固定成了一个中间点但计算距离时对某些商店用了右侧中位数对另一些用了左侧中位数导致前后不一致。修复方法就是统一用一个mid变量所有商店都和它做差。4.3 “下标越界或者读入错位”常见错误包括for (int i 0; i n; i)读入n个但数组开成a[n1]却从a[1]开始存读到a[n]没毛病但排序用了a.begin(), a.end()把下标0的空位置也排进去了导致中位数取错。或者反过来开vectorint a(n)后用for (int i1; in; i) cin a[i]越界了但在本地编译器不报错拿OJ上一跑就是RE。我建议读入直接for (int i0; in; i)存进a[0]到a[n-1]这样和容器的迭代器完全对齐不会有错位。如果你偏爱1-indexed那排序就用sort(a.begin() 1, a.end())取值用a[n/2 1]也完全没问题但一定要保持统一。4.4 扩展一带权货仓选址怎么做如果把题目升级一下每个商店不是等权重而是有一个需求量w[i]要让“货仓到每个商店的距离乘以该商店的权重”之和最小问货仓放哪。这个问题的答案是带权中位数。做法是按坐标排序后从左到右累加权重当累加权重第一次大于等于总权重的一半时那个位置就是货仓选址。听起来很绕其实道理和普通中位数一样只是每个点的“影响力”不同了。普通中位数相当于所有权重都为1累加到一半就是正中间带权中位数就是按权重累加到一半。这个扩展在“糖果传递”“环形均分纸牌”等问题里经常出现值得掌握。4.5 扩展二二维曼哈顿距离选址更进一步如果商店分布在二维平面货仓到每个商店的距离用曼哈顿距离衡量|x1-x2| |y1-y2|那么由于曼哈顿距离在x和y方向是独立的整个最小化问题可以被拆成两个独立的一维问题x坐标单独做一次中位数y坐标单独做一次中位数最终选址的x就是所有商店x坐标的中位数y就是所有商店y坐标的中位数。这看起来像是高维扩展实际上还是同一个模型掌握了基础版本之后这类题就是加个循环的事。5. 一点比赛经验与个人体会这道题我在初学算法时也踩过“平均数”的坑后来被对拍程序狠狠教育了一次才真正理解绝对值和平方和的区别。刷题这件事最忌讳的就是背结论不求甚解。中位数这个结论你能背但换一个“带权”问你你还能不能推导出来如果能说明你真的懂了如果不能建议回去把前面那个“剥皮证明”自己动手写出完整推导过程写一遍胜过看十遍。另外想分享一个小技巧做这种“求最优位置”的题如果一时想不明白可以先写一个O(N^2)的暴力枚举用来验证后续优化算法的正确性。比赛时时间紧张但平时刷题一定要养成对拍的习惯。我个人的体会是一道题你就算不看题解用暴力对拍的方式自己猜结论、验结论比直接背题解要牢靠得多。货仓选址这道题就是这样暴力枚举每一个商店坐标作为货仓算一遍距离和你会发现最小值恰好出现在中位数附近——一旦观察到这个规律再去想证明整个思路就顺了。最后再说说代码风格。竞赛题很多时候不差这几毫秒但代码的清晰度直接影响你调试的效率。变量名别乱写中位数就叫mid答案就叫ans累加就用long long读入用while (cin n)兼容多组数据。这些习惯看起来不起眼等你在赛场上因为一个int溢出卡了半小时就会明白这些细节有多重要。 
长河君 · 2026/9/15 6:11:24 · 阅读 1.2k 货仓选址为什么排序后取中位数？经典贪心模型全解析
这道题出自《算法竞赛进阶指南》0x05排序章节原题是AcWing 104货仓选址题目很短但背后藏着一个很有意思的贪心模型。很多初学者第一次见到它第一反应是“货仓选址是不是得用动态规划或者三分”结果一看题解好家伙排序之后取中位数就结束了。今天我把这道题从读题到证明到代码到踩坑整个捋一遍包括为什么是中位数、偶数情况怎么选、代码写long long的原因、以及它和带权中位数、二维曼哈顿选址这类扩展问题之间的关系。如果你正在刷竞赛入门题或者刚学完排序想找点“排序不只是排个序”的感觉这篇应该能帮到你。1. 先说结论货仓选址到底在考什么1.1 一句话还原题目别被“选址”两个字吓到题目描述非常简短数轴上有N家商店坐标分别是A[1]到A[N]现在要在数轴上选一个位置建货仓使得货仓到所有商店的距离之和最小输出这个最小距离和。注意这里的“数轴”就是一维直线不是二维地图。很多同学第一次看到“选址”可能会脑补成平面几何、曼哈顿距离、甚至最短路径其实都不是。它就是一个纯粹的数学最优化问题给定N个点找一个点x让 |x - A1| |x - A2| ... |x - An| 最小。这个式子里只有绝对值加法没有任何复杂限制。所以它考察的本质是两个东西排序以及一个非常经典的贪心结论——中位数。排序在这里承担的角色是“把无序坐标变成有序序列”有了有序序列才能让中位数的性质自然浮现出来。这也是为什么《算法竞赛进阶指南》把它放在排序这一章而不是数学或贪心章节的原因表面上是在排序实际上是利用排序为后续的贪心决策做准备。1.2 为什么答案就是中位数而不是平均数先给结论把所有A[i]从小到大排序取中位数作为货仓位置距离和最小。如果N是奇数中位数唯一如果N是偶数中间两个数之间的任意一个位置都可以距离和一样。这个结论很多同学能背下来但心里没底因为直觉上会觉得“平均数是不是更好”。我举一个反例就明白了商店坐标是1、2、100。平均数约34.3距离和是 |34.3-1| |34.3-2| |34.3-100| ≈ 33.3 32.3 65.7 ≈ 131.3。但取中位数2距离和是 |2-1| |2-2| |2-100| 1 0 98 99。明显中位数更小。为什么平均数不行因为距离函数是绝对值的和不是平方和。平均值最小化的是平方误差中位数最小化的是绝对误差。两者有本质区别平方误差会把离群点放大所以平均数会被极端值“拉过去”而绝对误差对离群点的惩罚是线性的所以不会被极端值绑架。这个差异在数据分布偏斜时非常明显。所以在“距离和”这种衡量方式下中位数是天然的最优解。2. 从读题到算法排序在这里的真正角色2.1 排序是手段不是目的拿到题之后先想想不排序行不行。如果不排序N个点乱序摆在数轴上我们很难直接看出哪个位置是“中间”的。但一旦排序问题立刻变成“在有序序列里找一个位置使得到所有点的距离和最小”这时候就可以用数学方法直接推导。严格证明可以这样想先把排序后的商店坐标记作a1 a2 ... an。假设货仓选在x。我们只看最外面的两个商店a1和an如果x a1那么货仓到a1和an的距离之和是 (a1 - x) (an - x) a1 an - 2x显然x越大这个和越小所以x不应该小于a1。同理x如果大于an也应该往回收。所以最优x一定落在[a1, an]区间内。在这个区间内a1和an这一对点对答案的贡献是(an - a1)这是一个常数不受x影响。于是问题缩小为在剩下的a2到a(n-1)这N-2个点里选x使得到它们的距离和最小。依此类推每次剥掉最外面一对最优x都落在被剥掉区间之内。最后如果N是奇数会剩下正中间那一个点x只能等于它如果N是偶数会剩下中间两个点x在它们之间任意位置都行。这个剥皮式的证明非常直观也解释了为什么答案是中位数。2.2 中位数的两种取法怎么实现最省事具体实现时有一个小坑中位数到底取哪个下标。假设数组是0-indexed排序后长度为n。当n是奇数比如n5中位数是a[2]。当n是偶数比如n4中位数理论上可以是a[1]到a[2]之间的任何值代码里习惯上取a[2]即a[n/2]或者a[1]即a[(n-1)/2]都行因为距离和一样。很多题解写 ans abs(a[i] - a[n/2])也就是统一取排序后下标为n/2的元素。为什么不是a[(n-1)/2]其实两种写法在这个题里答案完全相同。但取a[n/2]有个好处当n为奇数时n/2就是正中间那个规范当n为偶数时n/2是中间偏右那个虽然和中间偏左那个计算结果一样但代码更统一。实际用哪个都无所谓关键是计算距离和时所有商店都用同一个mid做差不能一会儿用a[n/2]一会儿用a[(n-1)/2]。另外有人会问偶数情况是不是选中间两个数之内的任意点都行是的。比如商店在0和10货仓设在5距离和是10设在3距离和也是10设在-1距离和是12就不行了。因为中间两个端点之间的区间内一对最外点的贡献恒为(an - a1)不会多也不会少。但代码实现时我们只需要输出距离和所以选哪个中位数其实无所谓只要计算正确答案就正确。3. 完整实现与细节处理3.1 C标准写法新手照着抄就行直接给出最常规的写法#include bits/stdc.h using namespace std; int main() { int n; cin n; vectorlong long a(n); for (int i 0; i n; i) cin a[i]; sort(a.begin(), a.end()); long long mid a[n / 2]; long long ans 0; for (int i 0; i n; i) { ans llabs(a[i] - mid); } cout ans endl; return 0; }核心就三行排序、取中位数、累加绝对值。这里有几个细节值得展开说。第一为什么要用vectorlong long而不是vectorint。题目的坐标范围在不同OJ上不一样有的坐标给到1e9N给到1e5那么最大距离和大约是1e14级别已经超过int的2.1e9上限所以必须用long long。如果不注意直接在int下累加大数据的测试点一定会WA。第二llabs是long long版本的绝对值。直接用abs在某些编译器下可能被当作int处理虽然很多情况下能隐式转换但严谨一点还是用llabs。或者你也可以写a[i] mid ? a[i] - mid : mid - a[i]效果一样。第三排序用sort就够了。N最大也就是1e5左右O(N log N)的排序完全没问题没必要上什么复杂度更低的算法。在竞赛中简洁和正确永远是第一位的。3.2 不排序的进阶写法nth_element到底怎么回事如果你已经把这道题刷得很熟或者遇到N特别大、O(N log N)被卡的情况可以考虑用nth_element来找中位数它的平均复杂度是O(N)。#include bits/stdc.h using namespace std; int main() { int n; cin n; vectorlong long a(n); for (int i 0; i n; i) cin a[i]; nth_element(a.begin(), a.begin() n / 2, a.end()); long long mid a[n / 2]; long long ans 0; for (int i 0; i n; i) { ans llabs(a[i] - mid); } cout ans endl; return 0; }nth_element的作用是把数组重新排列使得第n/2个位置从0开始的元素正好是“序列按升序排序后该位置应该有的元素”并且它左边的元素都不大于它右边的元素都不小于它。但它不会完全排序整个数组所以O(N)的平均复杂度。要注意的是nth_element是一个部分排序算法它会改变数组内容而且不保证左右两边各自有序。如果你后面还需要整个数组有序就不要用它。另外它在C标准库里的实现平均很快但并不是严格意义上的“保证O(N)”最坏情况下也可能退化为O(N^2)只是实际竞赛中很少遇到。从学习角度讲我建议先把sort版写好、完全理解了再玩nth_element。因为这道题核心是中位数性质而不是选择算法本身。直接用sort最稳等以后遇到类似“动态中位数”“对顶堆”这类问题再慢慢接触更高级的数据结构。3.3 边界条件和多组输入处理这道题的边界条件比想象中多新手容易在这里丢分。第一只有一个商店。n1时中位数就是a[0]距离和是0代码天然正确不用特判。第二多个测试用例。有些OJ版本会说“有多组数据每组第一行一个整数N”此时你需要写成while (cin n)或while (scanf(%d, n) ! EOF)不要只读一次。我见过不少同学把while写成if然后样例过了交上去只有第一组对后面全WA。第三坐标是否包含负数。距离和涉及绝对值负数不影响处理llabs(a[i] - mid)会正确给出非负值。但如果你为了省事写了abs(a[i] - mid)且坐标差超过int范围同样会溢出所以还是老实long long。第四1-indexed和0-indexed容易混淆。如果你用for (int i 1; i n; i)读入中位数下标就是a[(n 1) / 2]取上整或者统一a[n / 2 1]。不要读入用1计算用0写出来乱成一团。我个人的建议是全程0-indexed代码最干净。4. 常见问题与排查技巧实录4.1 “我用的平均数为什么样例过了但提交不过”这是最经典的错法之一。原因前面已经讲过平均数和绝对距离和根本不对应。有的同学可能在小数据上碰巧平均数和中位数一样比如对称分布的数据1、2、3平均数是2中位数也是2距离和都是4样例过了就以为算法对。但一旦数据变成1、2、100立刻露馅。如果你怀疑自己是不是想错了最快的验证方式是暴力枚举把所有可能的货仓位置比如商店坐标的最小值到最大值之间的每个整数都算一次距离和看哪个最小。拿暴力代码和你的贪心代码对拍一旦出差异马上就能定位问题。尤其是刚学贪心的时候对拍是训练直觉的好工具不要觉得麻烦。4.2 “偶数个商店时我的答案和题解不一样”先说结论如果题解输出的是最小距离和那么无论选中位数偏左还是偏右距离和都是一样的不可能不一样。如果不一样大概率是你计算距离和时“混搭”了。举个例子商店坐标1、3、7、9。如果货仓选在3距离和是 |1-3| |3-3| |7-3| |9-3| 2 0 4 6 12。如果选在7距离和是6 4 0 2 12。如果选在5距离和是4 2 2 4 12。确实一样。偶数情况最优值是一个常数任何位于中间两个数之间的位置都可以。那为什么你算出来不一样很可能是你把货仓位置固定成了一个中间点但计算距离时对某些商店用了右侧中位数对另一些用了左侧中位数导致前后不一致。修复方法就是统一用一个mid变量所有商店都和它做差。4.3 “下标越界或者读入错位”常见错误包括for (int i 0; i n; i)读入n个但数组开成a[n1]却从a[1]开始存读到a[n]没毛病但排序用了a.begin(), a.end()把下标0的空位置也排进去了导致中位数取错。或者反过来开vectorint a(n)后用for (int i1; in; i) cin a[i]越界了但在本地编译器不报错拿OJ上一跑就是RE。我建议读入直接for (int i0; in; i)存进a[0]到a[n-1]这样和容器的迭代器完全对齐不会有错位。如果你偏爱1-indexed那排序就用sort(a.begin() 1, a.end())取值用a[n/2 1]也完全没问题但一定要保持统一。4.4 扩展一带权货仓选址怎么做如果把题目升级一下每个商店不是等权重而是有一个需求量w[i]要让“货仓到每个商店的距离乘以该商店的权重”之和最小问货仓放哪。这个问题的答案是带权中位数。做法是按坐标排序后从左到右累加权重当累加权重第一次大于等于总权重的一半时那个位置就是货仓选址。听起来很绕其实道理和普通中位数一样只是每个点的“影响力”不同了。普通中位数相当于所有权重都为1累加到一半就是正中间带权中位数就是按权重累加到一半。这个扩展在“糖果传递”“环形均分纸牌”等问题里经常出现值得掌握。4.5 扩展二二维曼哈顿距离选址更进一步如果商店分布在二维平面货仓到每个商店的距离用曼哈顿距离衡量|x1-x2| |y1-y2|那么由于曼哈顿距离在x和y方向是独立的整个最小化问题可以被拆成两个独立的一维问题x坐标单独做一次中位数y坐标单独做一次中位数最终选址的x就是所有商店x坐标的中位数y就是所有商店y坐标的中位数。这看起来像是高维扩展实际上还是同一个模型掌握了基础版本之后这类题就是加个循环的事。5. 一点比赛经验与个人体会这道题我在初学算法时也踩过“平均数”的坑后来被对拍程序狠狠教育了一次才真正理解绝对值和平方和的区别。刷题这件事最忌讳的就是背结论不求甚解。中位数这个结论你能背但换一个“带权”问你你还能不能推导出来如果能说明你真的懂了如果不能建议回去把前面那个“剥皮证明”自己动手写出完整推导过程写一遍胜过看十遍。另外想分享一个小技巧做这种“求最优位置”的题如果一时想不明白可以先写一个O(N^2)的暴力枚举用来验证后续优化算法的正确性。比赛时时间紧张但平时刷题一定要养成对拍的习惯。我个人的体会是一道题你就算不看题解用暴力对拍的方式自己猜结论、验结论比直接背题解要牢靠得多。货仓选址这道题就是这样暴力枚举每一个商店坐标作为货仓算一遍距离和你会发现最小值恰好出现在中位数附近——一旦观察到这个规律再去想证明整个思路就顺了。最后再说说代码风格。竞赛题很多时候不差这几毫秒但代码的清晰度直接影响你调试的效率。变量名别乱写中位数就叫mid答案就叫ans累加就用long long读入用while (cin n)兼容多组数据。这些习惯看起来不起眼等你在赛场上因为一个int溢出卡了半小时就会明白这些细节有多重要。