题目描述

出题是一件痛苦的事情!

相同的题目看多了也会有审美疲劳,于是我舍弃了大家所熟悉的 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% 的数据,1N20001 \leq N \leq 2000

对于 100% 的数据,1N2×1051 \leq N \leq 2 \times 10^5

保证所有输入数据绝对值小于 2302^{30} ,且 C1C \ge 1

题目分析

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

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

Q.E.D.


( ノ^ω^)ノ゚ 稻 花 香 里 说 丰 年 , 听 取 WA 声 一 片 。(╥╯^╰╥)