【题目来源】
洛谷：P1102 A-B 数对 - 洛谷
【题目描述】
给出一串正整数数列以及一个正整数 \(C\)，要求计算出所有满足 \(A-B=C\) 的数对的个数（不同位置的数字一样的数对算不同的数对）。
【输入】
输入共两行。
第一行，两个正整数 \(N,C\)。
第二行，\(N\) 个正整数，作为要求处理的那串数。
【输出】
一行，表示该串正整数中包含的满足 \(A-B=C\) 的数对的个数。
【输入样例】
4 1
1 1 2 3
【输出样例】
3
【解题思路】
【算法标签】
《洛谷 P1102 A-B数对》 #模拟# #数学# #二分# #排序# #哈希,hash# #双指针,two-pointer#
【代码详解】
#include <bits/stdc++.h>
using namespace std;// 全局变量：
// n: 数组长度
// c: 目标差值
// a[200005]: 存储输入数组
// sum: 临时存储满足条件的元素个数
// ans: 存储最终结果（满足条件的对数）
int n, c, a[200005], sum;
long long ans = 0;/*** 二分查找左边界（第一个等于q的元素）* @param q 要查找的值* @return 第一个等于q的元素位置，未找到返回0*/
int findleft(int q)
{int l = 1, r = n + 1;while (l < r){int mid = l + (r - l) / 2; // 防止溢出的中间值计算if (a[mid] >= q){r = mid;}else{l = mid + 1;}}if (a[l] == q){return l;}else{return 0;}
}/*** 二分查找右边界（最后一个等于q的元素）* @param q 要查找的值* @return 最后一个等于q的元素位置，未找到返回0*/
int findright(int q)
{int l = 1, r = n + 1;while (l < r){int mid = l + (r - l) / 2;if (a[mid] <= q){l = mid + 1;}else{r = mid;}}if (a[l - 1] == q){return l - 1;}else{return 0;}
}int main()
{// 输入数组长度和目标差值cin >> n >> c;// 输入数组元素for (int i = 1; i <= n; i++){cin >> a[i];}// 对数组进行排序sort(a + 1, a + n + 1);// 枚举每个元素作为B，查找满足A=B+c的元素for (int i = 1; i <= n; i++){int q = a[i] + c; // 计算需要查找的值// 查找该值的左右边界if (findleft(q) == 0 && findright(q) == 0){sum = 0; // 没有找到满足条件的元素}else{sum = findright(q) - findleft(q) + 1; // 计算满足条件的元素个数}ans += sum; // 累加到最终结果}// 输出满足条件的对数cout << ans << endl;return 0;
}
// 使用lower_bound和upper_bound重写一遍
#include <bits/stdc++.h>
using namespace std;// 全局变量：
// n: 数组元素个数
// c: 目标差值
// a[200005]: 存储数组元素
// sum: 临时变量（未使用）
// ans: 存储满足条件的元素对总数
int n, c, a[200005], sum;
long long ans = 0;int main()
{// 输入数组长度n和目标差值ccin >> n >> c;// 输入数组元素for (int i = 1; i <= n; i++){cin >> a[i];}// 对数组进行排序（升序）sort(a + 1, a + n + 1);// 遍历数组，统计满足a[j] = a[i] + c的元素对for (int i = 1; i <= n; i++){// 使用STL算法计算满足条件的元素个数：// upper_bound找到第一个大于a[i]+c的位置// lower_bound找到第一个不小于a[i]+c的位置// 两者相减即为等于a[i]+c的元素个数ans += upper_bound(a + 1, a + n + 1, a[i] + c) - lower_bound(a + 1, a + n + 1, a[i] + c);}// 输出满足条件的元素对总数cout << ans << endl;return 0;
}
【运行结果】
4 1
1 1 2 3
3