题解 P1102 【A-B 数对】

· · 题解

明明是一道双指针的好题...怎么题解里面全是暴力map

我们考虑题目要求求出所有A-B=C的数对，我们可以先将原数组排序，然后就会发现每个数A，对应的数B一定是一段连续的区间。

然后我们再考虑如何去找到这个区间。

我们显然是要找到这个连续区间的左端点和右端点。

考虑到排序之后序列的有序性，我们枚举每个数，他们的左端点和右端点都是单调不降的，因此我们可以用\text{two-pointers}，也就是双指针来维护这个东西。

具体的实现就是，我们维护两个右端点r1 , r2，每次r1右移到a[r1] - a[l] <= c的最后位置的下一位，r2右移到满足a[r2] - a[l] < c最后一位.

也就是说， 此时如果a[r2] - a[l] == c && a[r1 - 1] - a[l] == c，中间的那一段一定都是满足条件的，我们让ans += r1 - r2即可。

代码很简洁。

Code: 
#include <bits/stdc++.h>
#define ll long long

using namespace std;

const int N = 2e5 + 10;
int n , c;
int a[N];

int main () 
{
    cin >> n >> c;
    for(int i = 1 ; i <= n ; i ++) cin >> a[i];
    sort(a + 1 , a + 1 + n);
    int l = 1, r1 = 1 , r2 = 1;
    ll ans = 0;
    for(l = 1 ; l <= n ; l ++) {
        while(r1 <= n && a[r1] - a[l] <= c) r1 ++;
        while(r2 <= n && a[r2] - a[l] < c ) r2 ++;
        if(a[r2] - a[l] == c && a[r1 - 1] - a[l] == c && r1 - 1 >= 1)   
            ans += r1 - r2;
    }
    cout << ans;
    return 0;
}