烦恼的高考志愿

题意

有 m 所学校，每所学校有一个预计分数线；有 n 位学生，每位学生有一个估分。

对每位学生，要推荐一所分数线和他的估分差距最小的学校。这个最小差值就是该学生的不满意度。

要求输出所有学生不满意度之和。

思路

先看一个可以直接验证想法的朴素解：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27#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;
}

朴素做法对每个学生枚举所有学校，求最小绝对差。这个做法是 $O(nm)$ ，在 n,m <= 100000 时会超时。

把学校分数线排序后，对于一个学生分数 x，离它最近的学校只可能在分界点两侧：

第一个 >= x 的学校；
这个学校前面的学校。

rbook《二分查找》文章中把这类问题归为“最近元素”：先用 lower_bound 找分界点，再比较前驱和当前位置。

样例查找过程

样例学校分数线排序后为：

text

1513 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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19import 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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64/**
 * 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;
}

复杂度

排序学校分数线需要 $O(m log m)$ 。
每个学生做一次二分，需要 $O(log m)$ ，总共 $O(n log m)$ 。
总时间复杂度 $O(m log m + n log m)$ 。
空间复杂度 $O(n + m)$ 。

总结

这题的关键是把“最近”转成有序数组上的分界点问题。

二分找到第一个不小于目标值的位置后，不要只看这个位置，还要看它前面的那个位置。最近元素一定在这两个候选中。

目录

题意

思路

样例查找过程

Python 知识

代码

复杂度

总结