http://www.yyycode.cn/index.php/2020/07/03/p1102-a-b-%e6%95%b0%e5%af%b9/
https://www.luogu.com.cn/problem/P1102
出题是一件痛苦的事情！
相同的题目看多了也会有审美疲劳，于是我舍弃了大家所熟悉的 A+B Problem，改用 A-B 了哈哈！
好吧，题目是这样的：给出一串数以及一个数字 CC，要求计算出所有 A – B = CA−B=C 的数对的个数（不同位置的数字一样的数对算不同的数对）。
输入共两行。
第一行，两个整数 N, CN,C。
第二行，NN 个整数，作为要求处理的那串数。
一行，表示该串数中包含的满足 A – B = CA−B=C 的数对的个数。
输入 #1复制
4 1 1 1 2 3输出 #1复制
3对于 75\%75% 的数据，1 \leq N \leq 20001≤N≤2000。
对于 100\%100% 的数据，1 \leq N \leq 2 \times 10^51≤N≤2×105。
保证所有输入数据都在 3232 位带符号整数范围内。
2017/4/29 新添数据两组
刚开始做这题理解错二分了。二分是找单调递增序列a中查找x>=a的数中最小的一个(即x或者x的后继);另一个是找x或者x的前驱；在这道题比如
5 1 1 1 2 2 3
要写两个二分，一个找前驱，一个找后继，这样才能正确统计出有多少满足的。有重复数字的时候二分找的是前驱或者后继
A-B=C<—>A=B+C，我们枚举B，二分找A就可以了。O（nlogn）
#include<iostream> #include<vector> #include<queue> #include<cstring> #include<algorithm> using namespace std; const int maxn=2e5+100; typedef long long LL; LL a[maxn]; LL bsearch1(LL l,LL r,LL q) { //右边界 while(l<r) { LL mid=(l+r)>>1; if(a[mid]>=q) r=mid; else l=mid+1; } return l; } LL bsearch2(LL l,LL r,LL q) { //左边界 while(l<r) { LL mid=(l+r+1)>>1; if(a[mid]<=q) l=mid; else r=mid-1; } return l; } int main(void) { LL n,c;cin>>n>>c; for(LL i=1;i<=n;i++) cin>>a[i]; sort(a+1,a+1+n); LL sum=0; for(LL i=1;i<=n;i++) { LL t1=bsearch1(1,n+1,a[i]+c); LL t2=bsearch2(0,n,a[i]+c); if(t1==n+1||t2==0) continue; sum+=t2-t1+1; } cout<<sum<<endl; return 0; }
