题意

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

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

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

思路

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

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 找分界点，再比较前驱和当前位置。

样例查找过程

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

1513 567 598 689

这张表展示每个学生的左右候选和不满意度。

总不满意度是 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。

代码

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)))

复杂度

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

总结

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

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