企业官网建设流程全解析

做洛谷题库的时候，有一道题让我印象特别深刻，就是编号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[k+1]之间，那最近的无非是左边那个或右边那个。

换句话说，在一维数轴上，任意点到一组排好序的点中最近的那个，一定是它在有序序列里的左邻居或右邻居。这个性质是“排序+二分”能成立的根基。你可以想象一条马路上有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(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; vector<long 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是我二分专题练习里的第一道题，做完它之后，我再遇到“给我一堆点，反复问某个位置离哪个点最近”的题，第一反应都会是先排序。这个习惯帮我解决过不少看起来跟算法毫无关系的实际问题。如果你做完这题还觉得不过瘾，我建议你把学生数组也排序，用双指针再写一遍，然后和二分版本跑同一组随机数据对一下答案。两个版本的代码结构完全不同，但输出必须完全一致，这个过程比看懂十篇题解都有用。另外送你一个小技巧：做这一类绝对值求和题，先在草稿纸上画一条数轴，把所有点和查询位置标上去，边界情况基本一眼就能看全，代码自然不容易写错。