题目描述
出题是一件痛苦的事情!
相同的题目看多了也会有审美疲劳,于是我舍弃了大家所熟悉的 A+B Problem,改用 A-B 了哈哈!
好吧,题目是这样的:给出一串数以及一个数字 C,要求计算出所有 A - B = C 的数对的个数(不同位置的数字一样的数对算不同的数对)。
输入格式
输入共两行。
第一行,两个整数 N, C。
第二行,N 个整数,作为要求处理的那串数。
输出格式
一行,表示该串数中包含的满足 A - B = C 的数对的个数。
输入输出样例
输入 #1
4 1
1 1 2 3
输出 #1
3
说明/提示
对于 75% 的数据,$1 \leq N \leq 2000$ 。
对于 100% 的数据,$1 \leq N \leq 2 \times 10^5$ 。
保证所有输入数据绝对值小于 $2^{30}$ ,且 $C \ge 1$ 。
题目分析
题目要求计算出所有 A - B = C 的数对的个数(不同位置的数字一样的数对算不同的数对)。已知C,此时转换下等式可得到 A - C = B。我们可以尝试利用单调性对齐进行处理,若A呈单调增,由于C的值固定,所以B也是单调增的。我们可以提前对所有的数进行升序排列,以遍历到的a[i]
作为A,我们去统计与之匹配的a[i]-C
的个数,由于排序过,所以所有能匹配的a[i]-C
一定是连续的。
而由于单调性,a[i]
确定的答案区间$l_i \sim r_i$ 一定是与 a[i-1]
确定的答案区间$l_{i-1}\sim r_{i-1}$ 重叠或者在其右侧。这就不需要重复在$1\sim n$ 的范围内寻找和a[i]
对应的 a[i]-C
了,只需在之前答案的基础上往后找即可,这块的复杂度为$O(n)$的复杂度,整体复杂度为$O(nlogn)$。
代码实现
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N=2e5+5;
int a[N];
int n,c;
//a-b=c => a-c=b
int main(){
cin>>n>>c;
for(int i=1;i<=n;i++){
cin>>a[i];
}
sort(a+1,a+n+1);
int l=1,r=1;
long long sum=0;
for(int i=1;i<=n;i++){
int B=a[i]-c;
while(r<=n && a[r]<=B) r++;
while(l<=r && a[l]<B) l++;
sum+=(r-l);
}
cout<<sum;
return 0;
}