题目描述

给定 n 个整数和一个整数 C，求有多少对数 (a,b) 满足 a-b=C。

输入格式

第一行两个整数 n, C。 第二行 n 个整数。

输出格式

输出满足条件的数对数量。

样例输入

4 1
1 1 2 3

样例输出

3

解题提示

数据范围分层

75% 测试点：(1 < N < 2000) 100% 完整数据： 1 <N <2*10^5

1. 暴力双重循环（仅过 75% 数据）

思路：两层循环枚举所有有序数对 ((a_i,a_j))，判断是否满足 (a_i - a_j = C)，满足则计数 + 1 时间复杂度：(O(n^2)) 超时原因：当 (n=2\times10^5) 时，总运算量约 (4\times10^{10})，远超时间限制，仅小数据 (n\le2000) 可通过

2. 排序 + 二分查找（满分解法，(O(n\log n))）

先将数组升序排序； 遍历每一个元素当作等式中的 a，需要找到满足 (b = a - C) 的数字； 使用二分查找 lower_bound、upper_bound 快速算出数组中等于 b 的元素个数； 把每一轮查到的个数累加，即为最终答案。

复杂度说明：排序 (O(n\log n))，n 次二分每次 (O(\log n))，总复杂度 (O(n\log n))，可轻松通过 (2\times10^5) 大数据

额外坑点提示

数值范围 (a[i],C < 2^{30})，超出普通 int 存储上限，需使用 long long / unsigned long long 存数值； 答案总数可能很大，计数变量必须定义为 long long，防止整型溢出； n 达到 (2*10^5)，输入量大，建议添加

ios::sync_with_stdio(false); 
cin.tie(nullptr);

加速读入避免超时。