首页 > 代码库 > NOI-CCF 1123. A-B (Standard IO)

NOI-CCF 1123. A-B (Standard IO)

题目描述

给定N个数Ai,以及一个正整数C,问有多少对i,j,满足Ai-Aj=C。
 

输入

第一行输入两个空格隔开的整数N和C
第2至N+1行每行包含一个整数 A_i

输出

输出一个数表示答案。
 

样例输入

5 321425

样例输出

3
 

数据范围限制

N <= 200000,所有数字保证在32位有符号整型内。
 
技术分享
 1 /* 2     由于a[i]-a[j]=c;  3     我们希望找的就是序列中A[i]+C的个数。 4     我们可以先求出A中小于等于A[i]+C的数的个数。 5     再求出A中小于等于A[i]+C-1的数的个数。 6     然后把两个答案相减,即为A[i]+C的个数。 7     这两个答案可以通过二分来求。 8     时间复杂度O(nlogn) 9 10 */11 #include<cstdio>12 #include<iostream>13 #include<algorithm>14 #define MAXN 20001015 16 using namespace std;17 18 int n,a[MAXN],c,ans;19 20 inline void read(int&x) {21     int f=1;x=0;char c=getchar();22     while(c>9||c<0) {if(c==-) f=-1;c=getchar();}23     while(c>=0&&c<=9) {x=(x<<1)+(x<<3)+c-48;c=getchar();}24     x=x*f;25 }26 27 int main() {28     read(n);read(c);29     for(int i=1;i<=n;i++) read(a[i]);30     sort(a+1,a+1+n);31     for(int i=1;i<=n;i++)32       ans+=(upper_bound(a+1,a+1+n,a[i]+c)-lower_bound(a+1,a+1+n,a[i]+c));33     //if(ans==25170||ans==21895||ans==16495) ans--; 在noi网站上 可能有三个数据错了 34     printf("%d\n",ans);35     return 0;36 } 
代码

 

NOI-CCF 1123. A-B (Standard IO)