2498: 【例】【普及-】【P1102】A-B 数对

内存限制：128 MB 时间限制：1.000 S
评测方式：文本比较 命题人：
提交：11 解决：7

题目描述

给出一串正整数数列以及一个正整数 lns="http://www.w3.org/1998/Math/MathML">�，要求计算出所有满足 lns="http://www.w3.org/1998/Math/MathML">�−�=� 的数对的个数（不同位置的数字一样的数对算不同的数对）。

输入

输入共两行。

第一行，两个正整数 lns="http://www.w3.org/1998/Math/MathML">�,�。

第二行，lns="http://www.w3.org/1998/Math/MathML">� 个正整数，作为要求处理的那串数。

输出

一行，表示该串正整数中包含的满足 lns="http://www.w3.org/1998/Math/MathML">�−�=� 的数对的个数。

样例输入 复制 

4 1
1 1 2 3

样例输出 复制 

3

提示

对于 lns="http://www.w3.org/1998/Math/MathML">75% 的数据，lns="http://www.w3.org/1998/Math/MathML">1≤�≤2000。

对于 lns="http://www.w3.org/1998/Math/MathML">100% 的数据，lns="http://www.w3.org/1998/Math/MathML">1≤�≤2×105，lns="http://www.w3.org/1998/Math/MathML">0≤��<230,lns="http://www.w3.org/1998/Math/MathML">1≤�<230。 

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



来源/分类

提交提交记录统计露一手!