排序学校分数线后，对每个学生二分找到左右相邻候选，累加最近分数线差值。
OJ: luogu
题目 ID: P1678
难度:普及-
标签:二分排序模拟python
创建: 2026-06-18 19:23
更新: 2026-10-07 12:15
题意
有 m 所学校，每所学校有一个预计分数线；有 n 位学生，每位学生有一个估分。
对每位学生，要推荐一所分数线和他的估分差距最小的学校。这个最小差值就是该学生的不满意度。
要求输出所有学生不满意度之和。
思路
先看一个可以直接验证想法的朴素解：
cpp
#include <bits/stdc++.h>
using namespace std;
int school[1005], stu[1005];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int m, n;
cin >> m >> n;
for (int i = 1; i <= m; i++) cin >> school[i];
for (int i = 1; i <= n; i++) cin >> stu[i];
long long ans = 0;
for (int i = 1; i <= n; i++) {
int best = abs(school[1] - stu[i]);
for (int j = 2; j <= m; j++) {
best = min(best, abs(school[j] - stu[i]));
}
ans += best;
}
cout << ans << '\n';
return 0;
}朴素做法对每个学生枚举所有学校，求最小绝对差。这个做法是 n,m <= 100000 时会超时。
把学校分数线排序后，对于一个学生分数 x，离它最近的学校只可能在分界点两侧：
- 第一个
>= x的学校； - 这个学校前面的学校。
rbook《二分查找》文章中把这类问题归为“最近元素”：先用 lower_bound 找分界点，再比较前驱和当前位置。
样例查找过程
样例学校分数线排序后为：
text
513 567 598 689这张表展示每个学生的左右候选和不满意度。
| 学生估分 | 右侧第一个不小于它的分数线 | 左侧相邻分数线 | 最小差值 |
|---|---|---|---|
500 |
513 |
无 | 13 |
600 |
689 |
598 |
2 |
550 |
567 |
513 |
17 |
总不满意度是 13 + 2 + 17 = 32。
Python 知识
sorted(...)返回新的有序学校列表，保留输入切片的原值。bisect_left等价于 C++ 的lower_bound；返回位置左右两侧就是最近值的全部候选。math.inf作为不存在的左/右候选距离，使边界和普通情况共用一次min。sum(map(dissatisfaction, students))表达“逐个映射不满意度，再求和”。/home/rainboy/mycode/hugo-blog/content/program_language/python/sorting_and_ordering.md：sorted的返回值和排序语义。/home/rainboy/mycode/hugo-blog/content/program_language/python/map_reduce_filter.md：已有命名函数时使用map。
代码
python
import sys
from bisect import bisect_left
from math import inf
data = list(map(int, sys.stdin.buffer.read().split()))
m, n = data[:2]
schools = sorted(data[2:2 + m])
students = data[2 + m:2 + m + n]
def dissatisfaction(score):
index = bisect_left(schools, score)
lower = score - schools[index - 1] if index else inf
upper = schools[index] - score if index < m else inf
return min(lower, upper)
print(sum(map(dissatisfaction, students)))C++ 实现，使用 rbook《二分查找》模板的 first_true 加双哨兵：
cpp
/**
* Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
* rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
* rainboy的学习导航网站: https://idx.roj.ac.cn
* create_at: 2026-08-02 01:36
* update_at: 2026-08-02 01:36
*/
/* P1678 烦恼的高考志愿 */
/* 排序分数线后，对每个学生分数用 first_true 找第一个 >= score 的位置，再比较前后两个候选。 */
#include <bits/stdc++.h>
using namespace std;
const int MAXM = 100000 + 5;
int m, n; // m 所学校，n 位学生
int score; // 当前学生估分
int a[MAXM + 2]; // 分数线，a[0] 为 -INF 哨兵，a[m+1] 为 +INF 哨兵
// 检查 a[pos] 是否不小于当前学生估分。
bool check(int pos) {
return a[pos] >= score;
}
// 在 [l, r] 中查找第一个满足 check(pos) 的位置。
// 要求 check 单调：false false ... false true true ... true。
// 调用时要保证 r 是一个真实或虚拟的可行位置。
int first_true(int l, int r) {
while (l < r) {
int mid = l + (r - l) / 2;
if (check(mid)) r = mid;
else l = mid + 1;
}
return l;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> m >> n;
for (int i = 1; i <= m; ++i) cin >> a[i];
sort(a + 1, a + m + 1);
// 两个哨兵：保证二分查找永远不会越界。
a[0] = INT_MIN; // 虚拟位置 0：表示不存在 <= score 的元素
a[m + 1] = INT_MAX; // 虚拟位置 m+1：表示不存在 >= score 的元素
long long ans = 0;
while (n--) {
cin >> score;
// 第一个 >= score 的分数线位置，一定存在（最坏是 m+1 哨兵）
int pos = first_true(1, m + 1);
// 最近分数线只在 pos 和 pos-1 两个候选中，取差值的较小者
ans += min<long long>((long long)a[pos] - score, (long long)score - a[pos - 1]);
}
cout << ans << '\n';
return 0;
}STL 写法
C++ 标准库已经把“二分找边界”做成了 lower_bound：用 vector<ll> 装下所有学校的分数线，sort 排好序后，对每个学生分数调用 lower_bound 拿到第一个不小于它的位置，再和它的前一个位置比较差值。和上面手写 first_true 加双哨兵的写法相比，这里不用自己写二分循环、也不用摆哨兵，代价是要显式判断返回值是不是 begin() / end()，把两端边界分开处理。不满意度之和最大约 long long。
对应的 cppbook 章节：二分查找：是否存在与边界位置
cpp
/**
* Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
* rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
* rainboy的学习导航网站: https://idx.roj.ac.cn
* create_at: 2026-10-07 00:19
* update_at: 2026-10-07 00:19
*/
// 这是 STL 写法：用 vector<ll> 存下所有学校的预计分数线，sort 排好序后，
// 对每个学生分数用 lower_bound 定位第一个不小于它的分数线，再和它的前一个位置比较取较小差值。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll m, n; // m 所学校，n 位学生
vector<ll> a; // 排序后的学校预计分数线
// 返回分数线中与估分 x 相差最小的那个差值。
// lower_bound 返回第一个不小于 x 的位置 it，分三种情况：
// it == a.end() ：所有分数线都小于 x，离它最近的是最后一个元素；
// it == a.begin() ：所有分数线都不小于 x，离它最近的是第一个元素；
// 其余情况：最近分数线一定落在 *it 和 *(it - 1) 这两个候选里，取较小差值。
ll min_gap(ll x) {
auto it = lower_bound(a.begin(), a.end(), x);
if (it == a.end()) {
return x - *(it - 1);
}
if (it == a.begin()) {
return *it - x;
}
ll upper_gap = *it - x; // 右侧候选：第一个不小于 x 的分数线
ll lower_gap = x - *(it - 1); // 左侧候选：它前面的那条分数线
return min(upper_gap, lower_gap);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> m >> n;
a.resize(m);
for (ll i = 0; i < m; i++) {
cin >> a[i];
}
// 二分查找的前提是数据有序：先把分数线升序排好
sort(a.begin(), a.end());
ll ans = 0; // 不满意度之和最多约 1e5 * 1e6 = 1e11，累加变量必须用 ll
for (ll i = 0; i < n; i++) {
ll x;
cin >> x;
ans += min_gap(x);
}
cout << ans << '\n';
return 0;
}复杂度
- 排序学校分数线需要
。 - 每个学生做一次二分，需要
，总共 。 - 总时间复杂度
。 - 空间复杂度
。
总结
这题的关键是把“最近”转成有序数组上的分界点问题。
二分找到第一个不小于目标值的位置后，不要只看这个位置，还要看它前面的那个位置。最近元素一定在这两个候选中。