二分算法实战：A-B 数对与高考志愿问题解析

二、烦恼的高考志愿

2.1 题目背景

给定 m 所学校的录取分数线和 n 名学生的成绩，为每个学生分配一所学校，使得所有学生与学校分数差的绝对值之和最小。

2.2 解题思路

首先将学校的录取分数排序。针对每个学生的成绩 b，我们需要在录取分数中找到最接近的值。

使用二分查找找到第一个大于等于 b 的位置 pos。那么最优解要么在 pos 位置，要么在 pos - 1 位置。我们只需要比较这两个位置的差值绝对值即可。

边界处理细节： 在实际编码中，直接访问 pos 或 pos - 1 可能会越界。例如，如果所有分数都大于 b，pos 可能指向第一个元素，此时 pos - 1 无效；如果所有分数都小于 b，pos 可能超出数组范围。

解决方法是在数组两端添加哨兵值（左右护法），确保无论二分结果如何，访问下标都在合法范围内。

2.3 代码实现

// 烦恼的高考志愿
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;

typedef long long LL;
const int N = 1e5 + 10;
LL a[N], b[N];
int m, n;

// 手动实现二分查找，寻找第一个 >= x 的位置
LL find(LL x) {
    int l = 1, r = m;
    while (l < r) {
        LL mid = (l + r) / 2;
        if (a[mid] >= x) r = mid;
        else l = mid + 1;
    }
    return l;
}

int main() {
    cin >> m >> n;
    for (int i = 1; i <= m; i++) cin >> a[i];
    
    // 设置左哨兵，防止 pos-1 越界
    a[0] = -1e7;
    sort(a + 1, a + 1 + m);
    
    LL ret = 0;
    for (int i = 1; i <= n; i++) {
        cin >> b[i];
        LL pos = find(b[i]);
        // 比较 pos 和 pos-1 两个位置的距离
        ret += min(abs(a[pos] - b[i]), abs(a[pos - 1] - b[i]));
    }
    cout << ret << endl;
    return 0;
}

总结

通过以上两道题目，我们掌握了二分查找在统计匹配与最优距离计算中的核心应用。重点在于理解排序预处理的重要性，掌握 STL 二分函数的区间语义，以及在手动实现时如何通过哨兵值规避边界风险。二分法的本质是寻找二段性，代码虽简洁，但对逻辑严密性的要求很高。