厦门网站建设开发网站推广的工作内容
P1102 A-B 数对 【双指针（尺取法）】
题目描述
给出一串正整数数列以及一个正整数 C，要求计算出所有满足 A−B=C 的数对的个数（不同位置的数字一样的数对算不同的数对）。
输入格式
输入共两行。
第一行，两个正整数 N,C。
第二行，N 个正整数，作为要求处理的那串数。
输出格式
一行，表示该串正整数中包含的满足 A−B=C 的数对的个数。
输入输出样例
输入 #1
4 1
1 1 2 3
输出 #1
3
说明/提示
对于 75% 的数据，1≤N≤2000。
对于 100% 的数据，1≤N≤2×10^5 ，0≤ai<2^30 ，1≤C<2^30 。
以下基于使用双指针（尺取法）的解题思路:
- 先把数列升序排列
- k 指针负责枚举每个数
- i指针指向 a[i]-a[k]=c 的一段数的左端
- j指针指向 a[i]-a[k]=c 的这段数的右端+1
- ans 维护这段数的个数，ans += j-i
#include <bits/stdc++.h>
using namespace std;
long long n,c,ans=0;
long long a[200005];
int main()
{ cin>>n>>c;for(int i=1;i<=n;i++) cin>>a[i];sort(a+1,a+n+1);int i=1,j=1;for(int k=1;k<=n;k++){while(i<=n && a[i]-a[k]<c )i++;while(j<=n && a[j]-a[k]<=c)j++;ans+=j-i;}cout<<ans<<endl;return 0;
}