【GESP】C++五级练习题 luogu-P1102 A-B 数对
GESP C++ 五级练习题，二分查找考点应用，重点理解二分查找法和双指针法的应用。四-五级考生可以练习。题目难度⭐⭐☆☆☆，洛谷难度等级普及−。
luogu-P1102 A-B 数对
题目要求
题目背景
出题是一件痛苦的事情！
相同的题目看多了也会有审美疲劳，于是我舍弃了大家所熟悉的 A+B Problem，改用 A-B 了哈哈！
题目描述
给出一串正整数数列以及一个正整数 $C$，要求计算出所有满足 $A - B = C$ 的数对的个数（不同位置的数字一样的数对算不同的数对）。
输入格式
输入共两行。
第一行，两个正整数 $N,C$。
第二行，$N$ 个正整数，作为要求处理的那串数。
输出格式
一行，表示该串正整数中包含的满足 $A - B = C$ 的数对的个数。
输入输出样例 #1
输入 #1
1
2
3
4 1
1 1 2 3
输出 #1
1
3
说明/提示
对于 $75\%$ 的数据，$1 \leq N \leq 2000$。
对于 $100\%$ 的数据，$1 \leq N \leq 2 \times 10^5$，$0 \leq a_i <2^{30}$，$1 \leq C < 2^{30}$。
题目分析
题目本质是要求对于每一个数 $B$，找到数组中有多少个 $A$ 满足 $A = B + C$。
如果直接使用两层循环枚举 $A$ 和 $B$，在大数据量下（$N \leq 2 \times 10^5$）会超时（$O(N^2)$）。因此我们需要更高效的方法。 首先，将数组进行排序是所有高效解法的基础，这样可以将无序的查找转化为有序查找。
方法一：二分查找
思路：
- 排序数组。
- 遍历数组中的每一个数 $a[i]$ 作为 $B$。
- 计算出目标值 $target = a[i] + C$。
- 在数组中通过二分查找找到等于 $target$ 的起始位置和结束位置。
std::lower_bound：找到第一个 $\ge target$ 的位置。std::upper_bound：找到第一个 $> target$ 的位置。- 两个迭代器/指针相减，即为等于 $target$ 的元素个数。
- 累加所有个数即为答案。 时间复杂度：排序 $O(N \log N)$，每次查找 $O(\log N)$，共 $N$ 次，总复杂度 $O(N \log N)$。
方法二：双指针法
思路：
- 排序数组。
- 定义两个指针 $L$ 和 $R$，初始都指向数组开头。
- 遍历数组中的每一个数 $a[i]$ 作为 $B$，对应的目标是 $target = a[i] + C$。
- 利用数组的单调性：随着 $a[i]$ 增大，$target$ 也随之增大（或不变）。因此 $L$ 和 $R$ 只需要向右移动，不需要回退。
- 移动 $L$ 直到 $a[L] \ge target$。
- 移动 $R$ 直到 $a[R] > target$。
- 此时区间 $[L, R)$ 中的所有元素都等于 $target$，数量为 $R - L$。
- 累加答案。 时间复杂度：排序 $O(N \log N)$，双指针线性扫描 $O(N)$，总复杂度 $O(N \log N)$。
注意事项：
- 题目数据范围较大，数字本身和最终统计的答案
ans都有可能超过int上限，务必使用long long。 - 本题中“不同位置的数字一样的数对算不同的数对”，上述两种方法都正确处理了这一点（通过计算数量而不是判断存在性）。
示例代码
方法一、二分查找
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <algorithm>
#include <iostream>
// 使用 long long 防止溢出，C 的范围是 1 <= C < 2^30，A 和 B 同理
// 定义 long long 的别名 ll，方便编写
typedef long long ll;
// 全局数组，大小稍微开大一点防止越界
// N 最大 2*10^5
ll a[200005];
int main() {
// 优化 I/O 操作速度
std::ios::sync_with_stdio(false);
std::cin.tie(NULL);
int N;
ll C; // C 可能很大，用 ll
std::cin >> N >> C;
// 读取输入数组
for (int i = 0; i < N; i++) {
std::cin >> a[i];
}
// 排序是关键步骤。
// A - B = C => A = B + C
// 排序后，对于确定的 B，我们可以二分查找 A (即 B + C)
std::sort(a, a + N);
ll ans = 0;
// 遍历每一个数作为 B
for (int i = 0; i < N; i++) {
// 在 B 后面的位置寻找等于 B + C 的数的范围
// lower_bound 返回第一个 >= (a[i] + C) 的位置
// 注意：搜索范围 a + i + 1 到 a + N，因为 C >= 1，所以 A > B，A 一定在
// B后面
ll* start = std::lower_bound(a + i + 1, a + N, a[i] + C);
// upper_bound 返回第一个 > (a[i] + C) 的位置
ll* end = std::upper_bound(a + i + 1, a + N, a[i] + C);
// 两个指针相减即为中间等于 a[i] + C 的元素个数
// 如果找不到，start 和 end 会相等，结果为 0
ans += (end - start);
}
// 输出结果
std::cout << ans << std::endl;
return 0;
}
方法二、双指针法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <algorithm>
#include <iostream>
#include <vector>
const int MAXN = 200005;
long long a[MAXN];
int main() {
// 关闭同步，加速 IO
std::ios::sync_with_stdio(false);
std::cin.tie(NULL);
int n;
long long c;
std::cin >> n >> c;
for (int i = 0; i < n; i++) {
std::cin >> a[i];
}
// 1. 排序，为双指针或二分查找做准备
std::sort(a, a + n);
long long ans = 0;
int l = 0, r = 0;
// 2. 遍历每一个数作为 B (a[i])
for (int i = 0; i < n; i++) {
long long target = a[i] + c; // 我们要找的目标 A
// 寻找第一个 >= target 的位置 (l)
// 随着 a[i] 增大，target 也增大，l 只会向右移动，不需要回退
while (l < n && a[l] < target) {
l++;
}
// 寻找第一个 > target 的位置 (r)
// 同样，r 也只会向右移动
while (r < n && a[r] <= target) {
r++;
}
// 区间 [l, r) 中的所有元素都等于 target
if (l < n && a[l] == target) {
ans += (r - l);
}
}
std::cout << ans << std::endl;
return 0;
}
所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code
GESP 学习专题站：GESP WIKI
“luogu-”系列题目可在洛谷题库进行在线评测。
“bcqm-”系列题目可在编程启蒙题库进行在线评测。
欢迎加入：Java、C++、Python技术交流QQ群(982860385)，大佬免费带队，有问必答
欢迎加入：C++ GESP/CSP认证学习QQ频道，考试资源总结汇总
欢迎加入：C++ GESP/CSP学习交流QQ群(688906745)，考试认证学员交流，互帮互助
