本文主要是介绍洛谷 P1102 A-B 数对（二分查找），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目描述
出题是一件痛苦的事情！
相同的题目看多了也会有审美疲劳，于是我舍弃了大家所熟悉的 A+B Problem，改用 A-B 了哈哈！
好吧，题目是这样的：给出一串数以及一个数字 C，要求计算出所有 A - B = C 的数对的个数（不同位置的数字一样的数对算不同的数对）。
输入格式
输入共两行。
第一行，两个整数 N,C
第二行，N 个整数，作为要求处理的那串数。
输出格式
一行，表示该串数中包含的满足 A - B = CA−B=C 的数对的个数。
输入输出样例
输入 #1复制
4 1 1 1 2 3
输出 #1复制
3
说明/提示
对于 75% 的数据，1≤N≤2000。
对于 100% 的数据，1≤N≤2×10^5。
保证所有输入数据都在 32 位带符号整数范围内。
题目大意：给出一个数组以及一个整数C，从数组中任取两个数，分别为A，B，使A-B=C成立的方案总数。
分析：
1.暴力，暴力不太可能，如果暴力需要使用双层循环，这道题数据量在1e5级别，双层循环一定会超时。
2.比n^2小的时间复杂度一般是O(n*logn)或者O（n），n*logn说明有二分法是参与，我们把A-B=C移项，就可以发现，A=B+C,所以实际上题目可以转换为求解数组中的元素B+C的和A，在数组中有多少个。
所以只需要将数组排序，然后二分查找值都为A的区间的左端点L以及右端点R，A的数量就是R-L+1。
此外还有一个注意点：本题会爆int ,需要使用long long来计数.测试点4就是这个点。
代码如下：
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5;
int a[maxn];
int erfenL(int l,int r,int k)
{while(l<=r){int mid = (l+r)/2;if(a[mid]==k)r=mid-1;else if(a[mid]<k)l=mid+1;elser=mid-1;}if(a[r+1]==k)return r+1;return -1;
}
int erfenR(int l,int r,int k)
{while(l<=r){int mid=(l+r)/2;if(a[mid]==k)l=mid+1;else if(a[mid]<k)l=mid+1;elser=mid-1;}if(a[l-1]==k)return l-1;return -1;
}
int main()
{int n,c;cin>>n>>c;for(int i = 0;i<n;i++){scanf("%d",&a[i]);}sort(a,a+n);long long num = 0;for(int i = 0;i<n;i++){int x = a[i]+c;int l = erfenL(0,n-1,x);if(l==-1){continue;}else{int r = erfenR(0,n-1,x);num +=(r-l+1);}}cout<<num<<endl;return 0;
}
也可使用STL自带的upper_bound()和lower_bound()函数
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6+10;
int a[maxn];
int main()
{int n,c;cin>>n>>c;for(int i = 0;i<n;i++){scanf("%d",&a[i]);}sort(a,a+n);int num = 0;for(int i = 0;i<n;i++){int x = a[i]+c;int l = lower_bound(a,a+n,x)-a;if(l!=n){int r = upper_bound(a,a+n,x)-a;num+=r-l;}}cout<<num<<endl;return 0;
}
这篇关于洛谷 P1102 A-B 数对（二分查找）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
