小鱼干

V1

2022/05/02阅读:13主题:橙心

【题解】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% 的数据,

对于 100% 的数据,

保证所有输入数据绝对值小于 ,且

题目分析

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

而由于单调性,a[i] 确定的答案区间 一定是与 a[i-1]确定的答案区间 重叠或者在其右侧。这要就不需要重复在 的范围内寻找和a[i] 对应的 a[i]-C了,只需在之前答案的基础上往后找即可,这块的复杂度为 的复杂度,整体复杂度为

代码实现

#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;
}

分类:

后端

标签:

数据结构与算法

作者介绍

小鱼干
V1