luogu-P1678 烦恼的高考志愿

GESP C++五级练习，二分查找与排序的应用经典题目。题目要求为每位学生在已有的学校分数线中寻找相差最小的学校，累计最小不满意度。考察将暴力搜索优化为二分查找的能力以及大整数累加防溢出的技巧。难度⭐⭐。洛谷难度等级普及-。

luogu-P1678 烦恼的高考志愿

题目要求

题目描述

现有 $m$ 所学校，其中第 $i$ 所学校的预计分数线为 $a_i$ 。有 $n$ 位学生，其中第 $i$ 位学生的估分为 $b_i$ 。

根据 $n$ 位学生的估分情况，分别给每位学生推荐一所学校，要求学校的预计分数线和学生的估分相差最小（可高可低，毕竟是估分嘛），这个最小值为这位学生的不满意度。求所有学生的不满意度的和。

输入格式

第一行包含两个正整数 $m,n$ ，分别表示学校数和学生数。

第二行包含 $m$ 个非负整数 $a_1,a_2,\dots,a_m$ ，分别表示 $m$ 所学校的预计分数线。

第三行包含 $n$ 个非负整数 $b_1,b_2,\dots,b_n$ ，分别表示 $n$ 位学生的估分。

输出格式

输出一行一个非负整数，表示所有学生的不满意度的和。

输入输出样例 #1

输入 #1

4 3
513 598 567 689
500 600 550

输出 #1

说明/提示

数据范围：

对于 $30\%$ 的数据， $1\le n,m\le{10}^3$ ， $0\le a_i,b_i\le{10}^4$ ；
对于 $100\%$ 的数据， $1\le n,m\le{10}^5$ ， $0\le a_i,b_i\le{10}^6$ 。

题目分析

本题属于经典的 二分查找（Binary Search） 与 排序（Sorting） 结合应用题。题目给定了 $m$ 所学校录取分数线和 $n$ 个学生的估分，目标是为每个学生找到与其估分最接近的学校分数线，并计算全局最小不满意度总和。

1. 暴力解法与其局限性

最直观的想法是：对于每一个学生估分 $b_i$ ，遍历所有 $m$ 所学校的分数线 $a_1, a_2, \dots, a_m$ ，计算绝对值差 $|a_j - b_i|$ ，取其中的最小值。

时间复杂度：每个学生需要遍历 $m$ 所学校，处理 $n$ 个学生的时间复杂度为 $O(n \times m)$ 。
效率评估：当 $n, m \le 10^5$ 时，总计算次数约为 $10^5 \times 10^5 = 10^{10}$ 次。在标准 1 秒的时限内（通常允许 $10^8$ 次运算），暴力算法会严重超时（TLE）。

2. 二分查找优化思路

为了加快查找过程，我们可以利用单调性。如果我们把所有学校的预计分数线升序排列，那么对于任意学生的估分 $b_i$ ，距离 $b_i$ 最近的分数线必然位于刚好大于等于 $b_i$ 的学校或刚好小于 $b_i$ 的学校之中。

预处理排序：
- 将学校分数线数组 $a$ 进行升序排序，时间复杂度为 $O(m \log m)$ 。
定位最近分数线（二分查找）：
- 使用 C++ STL 标准库提供的 std::lower_bound 在有序数组 $a$ 中寻找第一个大于等于 $b_i$ 的元素位置（假设下标为 $pos$ ）。
- 离 $b_i$ 最近的值只有两种可能： $a[pos]$ （大于等于 $b_i$ 的最小值）或 $a[pos - 1]$ （小于 $b_i$ 的最大值）。
- 比较 $|a[pos] - b_i|$ 与 $|a[pos - 1] - b_i|$ ，取较小者累加至答案即可。
- 单次二分查找的时间复杂度为 $O(\log m)$ ，处理 $n$ 个学生总查找时间复杂度为 $O(n \log m)$ 。

总体时间复杂度： $O((m + n) \log m)$ 。当 $m, n = 10^5$ 时， $10^5 \log_2(10^5) \approx 1.7 \times 10^6$ 次计算，能够轻松在几毫秒内运行完成。

3. 边界条件判定

在使用 lower_bound 确定下标 $pos$ 时，需要注意以下边界问题：

估分低于所有学校（ $pos == 0$ ）：
- lower_bound 返回第一个元素下标 $0$ 。此时学生分数比所有学校都低，最近的学校只能是最低录取线 $a[0]$ ，绝对不能访问 $a[-1]$ （会导致数组越界）。
估分高于所有学校（ $pos == m$ ）：
- lower_bound 未找到大于等于 $b_i$ 的元素，返回结尾迭代器（对应下标 $m$ ）。此时学生分数比所有学校都高，最近的学校只能是最高录取线 $a[m - 1]$ 。
位于数组中间（ $0 < pos < m$ ）：
- $a[pos]$ 和 $a[pos - 1]$ 都有效，计算两者的绝对差并取最小值： $\min(|a[pos] - b_i|, |a[pos-1] - b_i|)$ 。

4. 易错点分析（数据溢出）

这是一个极易引起失分的隐蔽陷阱：

输入范围：学生数 $n \le 10^5$ ，分数差最大可达到 $10^6$ 。
最大总和：极端情况下，所有学生的不满意度累加和最大可达 $10^5 \times 10^6 = 10^{11}$ 。
类型范围：C++ 中标准 32 位 int 的最大值为 $2^{31} - 1 \approx 2.14 \times 10^9$ 。
结论：总和 $10^{11}$ 远超 int 表示上限，用于累加不满意度的变量 ans 必须使用 long long 类型，否则会产生溢出导致结果为负数或错误数值（WA）。

示例代码

方法一：使用 C++ STL `lower_bound`（推荐）

#include <algorithm> // 包含 std::sort 与 std::lower_bound
#include <cmath>     // 包含 std::abs 用于计算绝对值差
#include <iostream>  // 包含 std::cin 与 std::cout 输入输出
#include <vector>    // 包含 std::vector 动态数组

using namespace std;

int main() {
    // 关闭 cin/cout 与 C 标准输入输出的同步，解除 cin 与 cout 的绑定
    // 在处理 N, M 可达 10^5 的大量数据输入输出时，显著提升读写效率
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int m, n;
    // 读取学校数量 m 与学生数量 n
    if (!(cin >> m >> n)) return 0;

    // 创建大小为 m 的数组，保存 m 所学校的预计分数线
    vector<int> a(m);
    for (int i = 0; i < m; i++) {
        cin >> a[i];
    }

    // 1. 对学校预计分数线进行升序排序
    // 二分查找的前提条件必须是序列具有单调性（有序）
    sort(a.begin(), a.end());

    // 2. 累计所有学生的不满意度
    // 注意：所有学生不满意度的最大可能总和为 10^5 * 10^6 = 10^11，
    // 超过了 32 位 int 的最大值 (~2.14 * 10^9)，因此必须使用 64 位 long long
    long long total_dissatisfaction = 0;

    // 3. 逐个读入每位学生的估分并进行二分查找
    for (int i = 0; i < n; i++) {
        int b;
        cin >> b; // 读取第 i 位学生的估分

        // std::lower_bound 用于在升序区间 [a.begin(), a.end()) 内
        // 查找第一个大于等于估分 b 的学校分数线迭代器
        auto it = lower_bound(a.begin(), a.end(), b);
        // 通过 std::distance 计算该迭代器在 vector 中的下标位置 [0, m]
        int pos = distance(a.begin(), it);

        if (pos == 0) {
            // 情况一：学生估分 b 比所有学校的分数线都低
            // 最近的学校只能是最低录取线 a[0]，注意不能访问 a[-1]
            total_dissatisfaction += abs(a[0] - b);
        } else if (pos == m) {
            // 情况二：学生估分 b 比所有学校的分数线都高
            // lower_bound 返回 a.end()，下标 pos 为 m
            // 最近的学校只能是最高录取线 a[m - 1]
            total_dissatisfaction += abs(a[m - 1] - b);
        } else {
            // 情况三：学生估分 b 介于 a[pos-1] 与 a[pos] 之间
            // 离 b 最近的分数线必在小于等于 b 的最大值 a[pos-1]
            // 和大于等于 b 的最小值 a[pos] 之中产生
            int diff1 = abs(a[pos] - b);     // 计算与右侧大于等于 b 的学校的绝对差
            int diff2 = abs(a[pos - 1] - b); // 计算与左侧小于 b 的学校的绝对差
            total_dissatisfaction += min(diff1, diff2); // 取两者中的较小差值
        }
    }

    // 4. 输出所有学生最小不满意度的总和
    cout << total_dissatisfaction << "\n";

    return 0;
}

方法二：手写二分查找（理解二分原理）

如果你正在学习 GESP 五级二分查找的底层实现，也可以手写二分查找逻辑：

#include <algorithm> // 包含 std::sort
#include <cmath>     // 包含 std::abs
#include <iostream>  // 包含 std::cin 与 std::cout
#include <vector>    // 包含 std::vector

using namespace std;

/**
 * @brief 手写二分查找函数（等价于 std::lower_bound）
 * 
 * @param a 已排好序的升序数组
 * @param target 目标查找值（学生的估分 b）
 * @return int 第一个大于等于 target 的元素下标；若不存在则返回 a.size()
 */
int my_lower_bound(const vector<int>& a, int target) {
    int left = 0;
    int right = a.size() - 1;
    int ans = a.size(); // 初始值设为 a.size()，表示若所有元素都比 target 小时的默认返回值

    // 循环条件：左边界不超过右边界
    while (left <= right) {
        // 计算中间位置，采用 left + (right - left) / 2 可以防止 (left + right) 直接相加导致的数值溢出
        int mid = left + (right - left) / 2;

        if (a[mid] >= target) {
            ans = mid;       // 记录当前满足 >= target 的候选位置
            right = mid - 1; // 尝试在更左侧的区间寻找是否还有更靠前的合法位置
        } else {
            left = mid + 1;  // 当前值 a[mid] 小于 target，说明目标位置一定在 mid 右侧
        }
    }
    return ans; // 返回最终找到的第一个 >= target 的元素下标
}

int main() {
    // 快速输入输出优化
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int m, n;
    if (!(cin >> m >> n)) return 0;

    // 读入 m 所学校录取线
    vector<int> a(m);
    for (int i = 0; i < m; i++) {
        cin >> a[i];
    }

    // 1. 对学校录取线进行升序排序
    sort(a.begin(), a.end());

    // 2. 初始化总不满意度，必须为 long long 类型（防止累加溢出）
    long long total_dissatisfaction = 0;

    // 3. 处理每个学生的估分
    for (int i = 0; i < n; i++) {
        int b;
        cin >> b;

        // 使用手写的二分查找算法定位第一个大于等于 b 的学校下标 pos
        int pos = my_lower_bound(a, b);

        if (pos == 0) {
            // 下标为 0：估分低过所有学校，取录取线最低的学校 a[0]
            total_dissatisfaction += abs(a[0] - b);
        } else if (pos == m) {
            // 下标为 m：估分高过所有学校，取录取线最高的学校 a[m - 1]
            total_dissatisfaction += abs(a[m - 1] - b);
        } else {
            // 下标在 (0, m) 范围内：比较左侧 a[pos-1] 和右侧 a[pos]，累加较小绝对差
            int diff_right = abs(a[pos] - b);
            int diff_left = abs(a[pos - 1] - b);
            total_dissatisfaction += min(diff_right, diff_left);
        }
    }

    // 4. 输出答案
    cout << total_dissatisfaction << "\n";

    return 0;
}

复杂度对比与总结

解法	排序开销	查找开销	总时间复杂度	空间复杂度	结论
暴力枚举	无	$O(n \times m)$	$O(n \times m)$	$O(1)$	超时 (TLE)
二分查找	$O(m \log m)$	$O(n \log m)$	$O((m+n) \log m)$	$O(m)$	通过 (AC)

总结：

本题是二分查找算法在实际问题中灵活运用的经典范例。通过对学校录取线排序，成功将查找单个学生最优解的时间从线性 $O(m)$ 降到对数级 $O(\log m)$ 。
刷题时一定要注重数据规模与变量数据类型的匹配，养成用 long long 存储累加大整数的良好规范习惯。

本文由coderli.com原创，按照CC BY-NC-SA 4.0 进行授权
所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code
“luogu-”系列题目可在 洛谷题库 在线评测。
“bcqm-”系列题目可在 编程启蒙题库 在线评测。

GESP/CSP认证交流QQ群： 688906745

GESP/CSP 认证学习微信公众号

最后更新于 2026年8月16日

luogu-P1114 “非常男女”计划

luogu-P1678 烦恼的高考志愿