二分算法实战：A-B 数对与烦恼的高考志愿

简介

本文将通过两道经典二分查找例题 ——A-B 数对与烦恼的高考志愿，系统讲解二分查找的核心思想与实用技巧。涵盖排序预处理、lower_bound、upper_bound 的灵活运用，以及手动实现二分与边界细节处理。

一、A-B 数对

1.1 题目

链接：A-B 数对

1.2 算法原理

由于顺序不影响最终结果，所以可以先把整个数组排序，来研究是否有其他的性质。 由 A − B = C 得：B = A − C，由于 C 是已知的数，我们可以从前往后枚举所有的 A，然后去前面找有多少个符合要求的 B，正好可以用二分快速查找出区间的长度。

【STL 使用】

1. lower_bound：传入要查询区间的左右迭代器（注意是左闭右开的区间，如果是数组就是左右指针）以及要查询的值 k，然后返回该数组中 >= k 的第一个位置。
2. upper_bound：传入要查询区间的左右迭代器（注意是左闭右开的区间，如果是数组就是左右指针）以及要查询的值 k，然后返回该数组中 > k 的第一个位置；

例：a = [10, 20, 20, 20, 30, 40]，设下标从 1 开始计数，在整个数组中查询 20：lower_bound(a + 1, a + 1 + 6, 20)，返回 a + 2 位置的指针；upper_bound(a + 1, a + 1 + 6, 20)，返回 a + 5 位置的指针； 然后两个指针相减，就是包含 20 这个数区间的长度。

1.3 代码

#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; ret +=upper_bound(a +1,a + i +1,b)-lower_bound(a , a + i, b);}
 cout << ret << endl;
 return0;}