2498: 【普及-】【P1102】A-B 数对
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：1
解决：1
题目描述
给出一串正整数数列以及一个正整数 ，要求计算出所有满足 的数对的个数（不同位置的数字一样的数对算不同的数对）。
输入
输入共两行。
第一行，两个正整数 。
第二行， 个正整数，作为要求处理的那串数。
输出
一行，表示该串正整数中包含的满足 的数对的个数。
样例输入 复制
4 1
1 1 2 3样例输出 复制
3提示
对于 的数据，。
对于 的数据，，,。
#include<bits/stdc++.h>
using namespace std;
#define maxn 200010
typedef long long LL;
LL a[maxn];
int n,c;
int main(){
scanf("%d%d",&n,&c);
for (int i=0;i<n;i++)
scanf("%lld",&a[i]);
sort(a,a+n);
LL tot=0;
for(int i=0;i<n;i++)
tot +=upper_bound(a,a+n,a[i]+c)-lower_bound(a,a+n,a[i]+c);
//其实可以注意到lower_bound(a,a+n,a[i]+c+1)和upper_bound(a,a+n,a[i]+c)是等价的
printf("%lld",tot);
return 0;
}
#include<bits/stdc++.h>
using namespace std;
#define maxn 200010
typedef long long LL;
LL a[maxn];
int n,c;
int main(){
scanf("%d%d",&n,&c);
for (int i=0;i<n;i++)
scanf("%lld",&a[i]);
sort(a,a+n);
LL tot=0;
for (int i=0,L=0,R=0;i<n;i++) {
while (L<n&&a[L]<a[i]+c)
L++; //L相当于lower_bound，第一个a[L]>=a[i]+c的位置
while (R<n&&a[R]<=a[i]+c)
R++; //R相当于upper_bound，第一个a[R]>a[i]+c的位置
tot+=R-L;
}
printf("%lld",tot);
return 0;
}