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

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

二分查找是算法竞赛中的高频考点，核心在于利用数据的有序性或二段性快速定位目标。本文将通过 A-B 数对与烦恼的高考志愿两道经典例题，系统讲解从排序预处理到边界处理的完整思路。

A-B 数对

题目描述

给定一个整数数组和一个常数 C，求满足 A - B = C 的数对 (A, B) 的数量。顺序不影响结果。

解题思路

方程可变形为 B = A - C。由于 C 已知，我们可以枚举所有的 A，然后在数组中查找是否存在对应的 B。为了高效统计，先将数组排序。利用二分查找可以快速确定值为 B 的元素区间长度。

这里涉及两个 STL 函数：

• lower_bound：返回第一个大于等于 k 的位置。
• upper_bound：返回第一个大于 k 的位置。

两者相减即为值等于 k 的元素个数。注意 ST L 函数要求序列有序，且区间为左闭右开。

代码实现

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

typedef long long LL;
const int N = 2e5 + 10;
LL a[N];

int main() {
    int n, c;
    cin >> n >> c;
    for (int i = 1; i <= n; i++) cin >> a[i];
    
    // 排序是二分的前提
    sort(a + 1, a + 1 + n);
    
    LL ret = 0;
    for (int i = 2; i <= n; i++) {
        LL b = a[i] - c;
        // 在 [1, i] 范围内查找值为 b 的区间
        // lower_bound 找 >= b 的第一个位置
        // upper_bound 找 > b 的第一个位置
        ret += upper_bound(a + 1, a + i + 1, b) - lower_bound(a + 1, a + 1 + i, b);
    }
    cout << ret << endl;
    return 0;
}

提示：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 库函数还是手写实现，关键在于理解单调性与边界条件。掌握这两道典型题目后，面对类似的区间统计或最值逼近问题，便能迅速构建出高效的解决方案。