二分法

A-B 数对

题意

给出一个数组以及一个正整数C，找A和B，求A - B = C的个数（不同位置的数字一样的数对算不同的数对）

---

方法

简单描述

A-B=C 则 A-C=B
所以要枚举一个A，求出B有x个，答案+x

重点-如何找B

可以先sort，再用最后等于B的下标 - 第一个等于B的下标+1就可以啦，这里给一个样例说明

1 1 1 2 3 3 4

第一个1的下标是0，最后一个为1的下标是2，2-0+1=3个

---

重点

二分函数return的值很重要哦！

---

---

---

代码

#include <bits/stdc++.h>
using namespace std;
int a[200010]; 
int main(){
    int n , c;
    cin >> n >> c;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    } 
    sort(a+1, a+n+1);//先排序
    int l = 1;//区间左端点
    int r = 1;//区间右端点
    long long sum = 0;//符合条件A的总个数
    for(int i = 1; i <= n; i++){
        int t = a[i] + c;//t为A，a[i]为B，及B + C = A
        while(l <= n && a[l] < t) l++;  // 第一个 >= t的位置
        while(r <= n && a[r] <= t) r++; // 最后一个大于t的后一位
        if(a[l] == t && a[r-1] == t) sum += r-l;
    }
    cout << sum;
    return 0;
}