P1102 A-B数对

题目描述

出题是一件痛苦的事情！

相同的题目看多了也会有审美疲劳，于是我舍弃了大家所熟悉的 A+B Problem，改用 A-B 了哈哈！

好吧，题目是这样的：给出一串数以及一个数字 C，要求计算出所有 A - B = C 的数对的个数（不同位置的数字一样的数对算不同的数对）。

输入格式

输入共两行。

第一行，两个整数 N, C。

第二行，N 个整数，作为要求处理的那串数。

输出格式

一行，表示该串数中包含的满足 A - B = C 的数对的个数。

输入输出样例

输入 #1

4 1
1 1 2 3

输出 #1

3

说明/提示

对于 75% 的数据，$1 \leq N \leq 2000$ 。

对于 100% 的数据，$1 \leq N \leq 2 \times 10^5$ 。

保证所有输入数据绝对值小于 $2^{30}$ ，且 $C \ge 1$ 。

题目分析

题目要求计算出所有 A - B = C 的数对的个数（不同位置的数字一样的数对算不同的数对）。已知C，此时转换下等式可得到 A - C = B。我们可以尝试利用单调性对齐进行处理，若A呈单调增，由于C的值固定，所以B也是单调增的。我们可以提前对所有的数进行升序排列，以遍历到的a[i]作为A,我们去统计与之匹配的a[i]-C的个数，由于排序过，所以所有能匹配的a[i]-C一定是连续的。

而由于单调性，a[i] 确定的答案区间$l_i \sim r_i$ 一定是与 a[i-1]确定的答案区间$l_{i-1}\sim r_{i-1}$ 重叠或者在其右侧。这就不需要重复在$1\sim n$ 的范围内寻找和a[i] 对应的 a[i]-C了，只需在之前答案的基础上往后找即可，这块的复杂度为$O(n)$的复杂度，整体复杂度为$O(nlogn)$。

代码实现

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N=2e5+5;
int a[N];
int n,c;
//a-b=c => a-c=b
int main(){
    cin>>n>>c;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    sort(a+1,a+n+1);
    int l=1,r=1;
    long long sum=0;
    for(int i=1;i<=n;i++){
        int B=a[i]-c;
        while(r<=n &&  a[r]<=B) r++;
        while(l<=r && a[l]<B) l++;
        sum+=(r-l);
    }
    cout<<sum;
    return 0;
}