#STL013. 差值配对
差值配对
差值配对
工位上的测量表记录了 n 次读数。记录员想知道,有多少种方式可以指定“主读数”和“参照读数”,使主读数减去参照读数恰好为 C。两次读数必须来自不同记录,即使它们的数值相同也可以配对。
给定数组 a,统计有序下标对 (i,j) 的数量,要求 i≠j 且 a[i]−a[j]=C。交换 i、j 后是另一对;只有交换后的条件也成立时,才计入这另一对。
输入格式
第一行两个整数 n、C。第二行 n 个整数 a₁,…,aₙ。
输出格式
输出一行,一个整数,表示符合条件的有序下标对数量。答案需要使用 64 位有符号整数。
数据范围与约定
- 1≤n≤200000。
- 0≤C≤2000000000。
- −1000000000≤aᵢ≤1000000000。
- C=0 时,同值的不同下标均计入;某值出现 f 次,它贡献 f(f−1) 对。
样例 1
输入:
5 2
1 3 3 5 1
输出:
6
说明:值为 3 的主读数有两条,每条可选择两条值为 1 的参照读数,贡献 4;值为 5 的主读数可选择两条值为 3 的参照读数,贡献 2,共 6。
样例 2
输入:
4 0
7 7 2 7
输出:
6
说明:数值 7 出现三次,可选 3×2=6 个有序不同下标对;数值 2 只有一条,不能和自己配对。
原创说明
本题的场景、题面、样例、实现与数据由本题单作者独立编写;仅使用公开的算法概念与 C++ 标准库接口,未使用第三方题面或测试文件。