X002 A-B
大约 3 分钟
X002 A-B
【算法】 二分查找
【C++】 二分查找、upper_bound、lower_bound
【难度】 普及−
X002 A-B
一、题目简述
给出 个正整数和一个数 ,求满足 的数对 的个数。其中 和 都来自这 个数,且不同位置的相同数值算作不同的数对。
数据范围:,。
二、解题思路
问题转化
等价于 。也就是说,对于数组中的每个数 (把它当作 ),我们需要统计数组中有多少个元素等于 。这些元素都可以作为 与 配对。
由于不同位置的相同值算不同数对,每个 可以和每个等于 的 配对,所以答案 = 对每个 ,统计数组中值为 的元素个数,然后求和。
算法选择
把数组排序后,对于每个 ,值为 的元素会连续出现(如果有的话)。我们可以用 upper_bound 和 lower_bound 计算这个值的出现次数:
count = upper_bound(a+1, a+n+1, target) - lower_bound(a+1, a+n+1, target)lower_bound(...)返回第一个 的位置upper_bound(...)返回第一个 的位置- 两者之差即为 的出现次数
手动模拟
数组 ,,即求 。
- ,:数组中等于 0 的有 0 个
- (第二个),同上,0 个
- ,:数组中等于 1 的有 2 个(位置 1 和 2),贡献 2 对
- ,:数组中等于 2 的有 1 个,贡献 1 对
答案:。
验证所有满足 的数对: 第一组、 第二组(因为有两个 1)、,共 3 对。正确。
三、参考代码
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int a[N];
int main() {
int n, C;
cin >> n >> C;
for (int i = 1; i <= n; i++) cin >> a[i];
sort(a + 1, a + n + 1);
long long ans = 0; // 注意可能爆 int
for (int i = 1; i <= n; i++) {
int B = a[i] - C;
// 统计值为 B 的元素个数
ans += upper_bound(a + 1, a + n + 1, B) -
lower_bound(a + 1, a + n + 1, B);
}
cout << ans << endl;
return 0;
}四、复杂度分析
- 时间复杂度:排序 , 次二分查找每次 。总复杂度 。
- 空间复杂度:静态数组 。
五、知识扩展
为什么不直接双重循环?
,双重循环的复杂度 ,远超时间限制。
另一种解法:哈希表
如果不排序,也可以用 unordered_map 统计每个值的出现次数,然后遍历数组累加 。这是 的做法,但常数略大,且需要 C++11 以上的 unordered_map(注意哈希冲突风险)。
排序 + 二分的做法更稳妥,不需要额外的数据结构。
警惕溢出
数对个数可能达到 级别(例如所有元素相同且 时),答案需要用 long long 存储。
