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

提示：STL 二分仅适用于有序序列。若数据无序但具备二段性（如单调性），则需手动实现二分逻辑。

烦恼的高考志愿

题目描述

给定 m 所学校的录取分数线和 n 个学生的成绩，为每个学生找到录取分数与其成绩差值最小的学校，求所有学生最小差值的总和。

解题思路

首先对学校分数线进行排序。对于每个学生的成绩 b，我们需要在分数线中找到最接近的值。使用二分查找找到第一个大于等于 b 的位置 pos。

最优匹配点要么在 pos，要么在 pos - 1。计算这两个位置的差值绝对值，取较小者累加即可。

边界处理细节： 如果所有分数线都大于 b，pos 可能指向首元素，此时 pos - 1 越界；反之亦然。为了避免判断越界，可以在数组两端添加哨兵节点（左右护法），扩大搜索范围并简化逻辑。

代码实现

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;

typedef long long LL;
const int N = 1e5 + 10;
const LL INF = 1e7;

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];
    
    // 设置哨兵，防止边界越界
    a[0] = -INF;
    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 库函数还是手写实现，关键在于理解单调性与边界条件。掌握这两道典型题目后，面对类似的区间统计或最值逼近问题，便能迅速构建出高效的解决方案。