A-B 数对

题目背景

出题是一件痛苦的事情！

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

题目描述

给出一串正整数数列以及一个正整数 $C$，要求计算出所有满足 $A - B = C$ 的数对的个数（不同位置的数字一样的数对算不同的数对）。

输入格式

输入共两行。

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

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

输出格式

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

样例 #1

样例输入 #1

4 1
1 1 2 3

样例输出 #1

3

提示

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

对于 $100\%$ 的数据，$1 \leq N \leq 2 \times 10^5$，$0 \leq a_i <2^{30}$，$1 \leq C < 2^{30}$。

2017/4/29 新添数据两组

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

typedef long long ll;
const int N = 1e5 + 10;

ll a[N];

int n, c; 
int main()
{
    cin >> n >> c;
    for(int i = 1; i <= n;i++)
        scanf("%d", &a[i]);
    int r1 = 1, r2 = 1, l = 1, ans = 0;

    //维护两个右端点r1,r2,每次r1右移到a[r1] - a[l] <= c的最后位置的下一位,r2右移到满足a[r2] - a[l] < c最后一位. 
    //中间的那一段一定都是满足条件的，我们让ans += r1 - r2即可
    for(l = 1; l <= n; l++){
        while(r1 <= n && a[r1] - a[l] <= c)r1++;
        while(r2 <= n && a[r2] - a[l] < c)r2++;
        cout << r1  << " " << r2 << endl;
        ans += r1 - r2;

    }
    cout << ans << endl;

    return 0;
}