做洛谷题库的时候有一道题让我印象特别深刻就是编号P1678的“烦恼的高考志愿”。题面讲了一个很现实的场景高考出分之后每个考生拿着自己的估分在几十上百所学校的录取分数线之间来回比较想找到跟自己分数最接近的那所学校然后把所有考生的“不满意度”累加在一起。听起来像一道阅读理解剥开壳其实是一道非常标准的排序加二分练习题也是算法竞赛里“最近邻查询”最朴素的原型。这篇文章就当一次完整的做题记录。我会先带你建立数学模型再把复杂度算清楚最后给出两种能AC的写法并把我当年在这个题上交过的WA经历全部摊开来讲。无论你是准备蓝桥杯、CSP-J/S还是刚开始刷洛谷的二分专题这道题都值得静下心来吃透。先说明一下我记忆中的洛谷标准版输入是这样的第一行两个整数m和n第二行m个整数是各学校的录取分数线第三行n个整数是各考生的估分。后面所有代码都按这个顺序读入。1. 题目模型从“志愿烦恼”到数轴上的最近距离1.1 先把题面翻译成数学语言很多初学者看到“高考志愿”四个字就开始慌以为要模拟什么复杂的志愿匹配规则。实际上题目只问了一个问题对于每个考生a[i]在所有学校分数线b[j]中找到使|a[i] - b[j]|最小的那个j把这个最小值累加进答案。没有名额限制没有梯度志愿没有专业调剂就是一个纯粹的绝对值和最小化问题。所以整个题目的数学本质是给定一个有序点集B反复回答“查询点x到B中哪个点距离最近”的问题。B是学校的分数线x是考生的估分。考生数量n是查询次数学校数量m是点集大小。这个翻译过程非常重要。我见过太多人卡在这道题上不是因为算法不会而是因为始终被“志愿”两个字带着跑去想“如果这个学校分不够怎么办”“如果多个学校分数线一样怎么办”。这些生活化的疑问大部分在题目里根本不存在题目已经把条件简化到只剩绝对值距离了。做竞赛题的第一习惯应当是看清楚题目到底让你输出什么再把约束条件抽象成公式。1.2 一维最近邻的性质为什么答案的候选只有两个假设我们把所有学校分数线装进一个数组b从小到大排序。那么排完序后对于任意一个考生分数x它在数轴上的位置只有三种情况x比最小的分数线还小那最近的一定是b[0]x比最大的分数线还大那最近的一定是b[m-1]x落在某两个分数线b[k]和b[k1]之间那最近的无非是左边那个或右边那个。换句话说在一维数轴上任意点到一组排好序的点中最近的那个一定是它在有序序列里的左邻居或右邻居。这个性质是“排序二分”能成立的根基。你可以想象一条马路上有m家店每家店挂着一个最低消费额你手上有x块钱你不需要挨家挨户问“你们家我进不进得去”你只需要找到第一家“我可能进不去”的店再回头看上一家“我确定进得去”的店答案一定在这两家中间。这个性质不是高深数学它就是有序性带来的“局部性”。一旦理解了这层代码怎么写都不会跑偏。1.3 边界条件的直观理解我刚才说的三种情况对应到代码里就是三个分支。很多题解直接贴代码不解释为什么有if (pos 0)和if (pos m)导致初学者照抄后一遇到越界就懵。这里我提前把边界讲透当x比所有b都小二分查找会返回第一个位置0候选只有b[0]当x比所有b都大二分查找会返回“末尾哨兵位置m”候选只有b[m-1]当x夹在中间二分返回第一个b[pos] x的位置候选是b[pos]和b[pos-1]。这三个情况一个都不能少。少了边界轻则越界访问重则答案悄悄少算。这道理我当初也是用错误堆出来的后面第四节会详细讲。2. 复杂度账本为什么排序加二分能救你于水火2.1 朴素暴力到底有多慢最容易想到的写法就是两层循环对每个考生i遍历所有学校j维护一个最小值。代码三行就写完样例应该也能过。但你看一眼数据范围就知道不对劲m和n通常都在十万这个量级两层循环就是次比较。十万乘十万是多少一亿是1e8十万乘十万是1e10也就是一百亿次计算。即使编译器开了O2优化按每秒一亿次到几亿次运算算这个规模也要几十秒到几分钟。放在任何OJ上都是妥妥的超时。这还没算绝对值运算和min操作的开销实际只会更慢。我建议所有初学者养成一个条件反射看到数组长度出现1e5就必须考虑O(n^2)是否可行。1e5的平方是1e10是绝对的红线1e3的平方是1e6通常没问题。判断复杂度先看数量级这是刷题的基本功。2.2 排序加二分的复杂度拆解既然暴力的瓶颈在于每个查询都要从头扫一遍自然的想法就是让查询变快。把学校分数线排序之后每个考生就不再需要扫描全部学校而是用二分查找直接定位“第一个大于等于自己分数”的位置一次查找只需要比较O(log m)次。整体复杂度拆成两部分方案预处理每个查询总复杂度朴素双重循环无O(m)O(mn)排序 二分O(m log m)O(log m)O(m log m n log m)排序 双指针O(m log m n log n)均摊O(1)O(m log m n log n m n)从表格可以清楚看到二分方案把每个查询从O(m)降到了O(log m)。十万个学校log2(m)大约等于17也就是说每个考生最多只要比较十几次十万个考生总共一百多万次比较加上排序总操作量在千万级别。这在现代CPU上就是一瞬间的事。2.3 为什么排序之后不能用哈希可能会有人问能不能用哈希表把分数线存起来然后查一下估分是否恰好匹配某个学校答案是不能。因为题目要的是“差的绝对值最小”不是“恰好相等”。哈希表只能回答“有没有”回答不了“离我最近的是谁”。就像你问导航“离我最近的加油站有多远”导航不能只在你所在位置正上方搜一个加油站它必须做距离排序。这个问题的关键在于“距离”是一个度量概念它天然依赖数轴上的位置关系。一旦我们面对的是连续空间里的最近邻搜索排序和二分就是最自然的工具。哈希表应对的是精确匹配场景两者解决的是完全不同的问题。3. 完整可AC的实现从标准库到手写二分3.1 用C的lower_bound最省心的写法C标准库里有一个函数叫lower_bound作用是在有序数组里找到第一个不小于给定值的元素位置。它正好对应我们需要的“第一个分数线大于等于考生估分”的语义。先看完整代码#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int m, n; cin m n; vectorlong long school(m), student(n); for (int i 0; i m; i) cin school[i]; for (int i 0; i n; i) cin student[i]; sort(school.begin(), school.end()); long long ans 0; for (int i 0; i n; i) { long long x student[i]; int pos lower_bound(school.begin(), school.end(), x) - school.begin(); if (pos 0) { ans school[0] - x; } else if (pos m) { ans x - school[m - 1]; } else { ans min(school[pos] - x, x - school[pos - 1]); } } cout ans \n; return 0; }这段代码有两个容易被忽略但非常重要的细节。第一我把school和student都声明成了long long类型的vector。为什么是因为最终答案很可能超过int范围这一点第四部分还会展开。第二pos m这个分支处理的是“x比所有学校分数线都大”的情况这时候lower_bound返回的是end()迭代器实际下标正好是m直接判断即可不要再去访问school[m]。3.2 手写二分理解lower_bound内部在做什么有些场合不能直接用标准库或者你想彻底搞懂原理那就要能手写二分。手写版本和lower_bound完全等价的写法是左闭右开区间int l 0, r m; // 注意r初始化为m不是m-1 while (l r) { int mid (l r) / 2; if (school[mid] x) { r mid; } else { l mid 1; } } int pos l; // 此时l就是第一个x的位置关键区别在于当school[mid] x成立时我们把右边界收缩到mid说明“第一个x的位置”不可能在mid右边而mid本身可能正是答案当school[mid] x成立时mid这个位置肯定不满足条件直接排除所以左边界是mid 1。这样循环结束时l和r相等就是结果。把r初始化为m而不是m-1意义在于如果x比整个数组的最大值还大那么循环结束的位置会自然落在m上也就是“末尾哨兵”正好对应前面说的第三种边界情况。这种初始化方式省去了单独判断“是不是该返回m”的麻烦。我一开始写二分总爱用闭区间[l, r]在普通题里没问题但这道题里用左闭右开更顺滑因为允许返回m这个“虚下标”。3.3 同样思路的Python写法Python选手可以借助bisect模块逻辑和C几乎一一对应import bisect m, n map(int, input().split()) school list(map(int, input().split())) student list(map(int, input().split())) school.sort() ans 0 for x in student: pos bisect.bisect_left(school, x) if pos 0: ans school[0] - x elif pos m: ans x - school[-1] else: ans min(school[pos] - x, x - school[pos - 1]) print(ans)需要注意Python的bisect_left和C的lower_bound语义一样都是返回“第一个不小于x的位置”。如果你误用bisect_right那返回的是“第一个大于x的位置”在存在重复分数线的时候会算错。这道题虽然一般不会出现大量重复分数线但养成用bisect_left的习惯总没错。4. 我在评测记录里真实踩过的坑读反数组、溢出和越界4.1 第一个WA把学生分数和学校分数读反了这题我第一次提交的时候想着题目先提到学校就先把学校数组读进来结果把第二行和第三行的存储顺序搞反了我先把第二行存进student又把第三行存进school然后排序时排的是school查询时用的是student实际等价于拿学校分数去学生堆里找最近值整个逻辑全反了。最坑的是如果m和n相等样例数据又刚好长得对称这种错误在样例上完全看不出来只有提交大数据才会WA。后来我总结出一个习惯读入变量后马上写一行注释标明语义例如// school[i]是学校分数线student[i]是考生估分。别觉得注释多余这种低级错误在真实考试紧张状态下太容易犯了一块注释能省掉一次无效提交。另外建议给数组起表意明确的名字别用a、b、c这种无意义命名。这道题里我后来一直用school和student读错的可能性就小很多。4.2 第二个WA答案超了int范围第一次意识到要开long long是看到有个测试点返回的答案大得离谱。假设n是十万每个考生的不满意值最大可以到几十万甚至上百万加起来完全可能超过二十一亿的int上限。注意这里的溢出是静默发生的程序不会报错只是答案变成负数或者莫名其妙的小数。我把所有参与累加的变量都定义成long long学校分数线和考生分数也一样。有同学觉得分数线本身不大用int存就行这一点其实无所谓但统一用long long更省心也避免在表达式中发生隐式类型转换的隐患。C里两个int相减得到的还是int赋值给long long之前就已经溢出了所以最稳妥的做法是从存数据那一刻起就用long long。4.3 第三个坑lower_bound返回后直接解引用导致越界新手最容易犯的错是这样写int pos lower_bound(school.begin(), school.end(), x) - school.begin(); ans min(abs(school[pos] - x), abs(school[pos - 1] - x));这段代码在pos等于m时会访问school[m]在pos等于0时会访问school[-1]两个都是未定义行为。数组越界在C里不一定会立刻崩溃可能运气好读到脏数据然后答案完全错误也可能编译出来什么奇怪的结果。这就是为什么所有正确题解都先判断边界再访问元素。我的建议是凡是涉及二分查找结果做邻居比较的题先把返回下标的所有可能值在纸上标一遍。对于这题返回下标只有几种情况0、中间、m。对着三种情况分别写分支代码会多几行但绝对不出错。4.4 对拍用暴力程序验证二分程序如果做了上面这些修改还是WA最有效的排查方式就是对拍。写一个完全没有性能顾虑的暴力版本然后用随机小数据同时跑两个程序对比输出。我自己常用的对拍流程是这样的写一个solve_brute.cpp就是两层循环的朴素实现写一个solve_fast.cpp用二分实现用脚本随机生成m、n在1到20之间、分数值在1到100之间的小数据循环跑几百组用diff比较两个程序输出不一致就停下来输出这组数据。对拍能帮你把“以为是二分写错但其实题意理解错”的问题一并暴露出来。我当年对拍出来的第一个不一致就是读反数组造成的。两个程序逻辑都“正确”但都建立在对题意的错误理解上输出当然一样错。所以对拍前最好先自己读三遍题确认模型没错。4.5 用样例验证但不过度依赖样例最后一条关于调试的建议是样例只能证明程序能跑通一条路径不能证明所有路径。尤其像这道题样例大概率覆盖不到“所有学生分数都小于所有学校分数”或者“所有学生分数都大于所有学校分数”的极端情况。我会在本地自己构造这三组极端用例学生分数全比最小学校线还小答案应该是每个差的绝对值之和学生分数全比最大学校线还大答案同理学生分数恰好在两个学校线正中间这时候左右两个差相等min取哪个都行但程序不能崩。这些边界用例比样例更能暴露二分写法的问题。养成习惯之后很多题能少提交好几次。5. 跳出这题一维最近邻模型的三个变形方向5.1 变形一要求输出“最匹配的学校编号”有些题目不满足于只输出差值总和还要你输出每个考生到底匹配哪所学校。解法仍然是在二分得到的pos上做文章只是需要额外维护两份信息。一份是排序后每个学校对应的原始编号另一份是判断左右邻居谁更近时记录下对应的原始编号。如果左右两个方向距离相等就要看题目额外给出的规则。有的题目要求取编号小的有的要求取排序靠前的还有的要求输出所有可能选项。处理方式就是在比较时加上优先级例如if (diff_left diff_right) { // 取左边学校编号是id[pos - 1] } else if (diff_right diff_left) { // 取右边学校编号是id[pos] } else { // 按题目规则处理平局 }这个变形非常常见因为现实场景里“哪个学校离我最近”往往不只是数值计算还要带上业务规则。掌握这个写法之后很多带“最近基站”“最近服务器”背景的题你都能直接套。5.2 变形二等距时如何选择才能保证结果稳定一维最近邻有一个天然问题如果查询点落在两个点的正中间左右两个候选的距离相等。这时候如果题目只要求输出距离之和那么选左选右都不影响答案。但如果要求输出方案就必须制定一个确定性规则通常是选编号较小者或者选原始顺序中更靠前的一个。这个规则需要写进比较逻辑里而不是天然存在。我在写这类题时有一个技巧先不加平局处理用随机数据对拍看程序是否在平局时不稳定。如果稳定说明数据里可能没有严格平局如果不稳定再根据题目要求补平局规则。注意对拍脚本里生成数据时故意让很多点落在中间能更快暴露问题。5.3 变形三从一维最近邻到更复杂的最优匹配把题目再往上拔一层如果每个学校有名额上限每个考生只能去一个学校那就不是简单最近邻问题而是带约束的匹配问题贪心或网络流都有可能上场。一维最近邻只是这个家族里最简单的一档但正是因为简单它最适合用来建立“距离极小化”的直觉。我在后面刷到类似“最小生成树”“最短路”之类的题时经常回想起P1678里那个朴素思想把问题画在数轴上排序然后利用局部性减少比较次数。算法思维就是这样一层层搭起来的没有第一层后面全是空中楼阁。最后说点个人体会。P1678是我二分专题练习里的第一道题做完它之后我再遇到“给我一堆点反复问某个位置离哪个点最近”的题第一反应都会是先排序。这个习惯帮我解决过不少看起来跟算法毫无关系的实际问题。如果你做完这题还觉得不过瘾我建议你把学生数组也排序用双指针再写一遍然后和二分版本跑同一组随机数据对一下答案。两个版本的代码结构完全不同但输出必须完全一致这个过程比看懂十篇题解都有用。另外送你一个小技巧做这一类绝对值求和题先在草稿纸上画一条数轴把所有点和查询位置标上去边界情况基本一眼就能看全代码自然不容易写错。