#STL013. 差值配对

    ID: 5266 传统题 2000ms 256MiB 尝试: 2 已通过: 1 难度: 2 上传者: 标签>原创STL专项unordered_map计数有序下标对

差值配对

差值配对

工位上的测量表记录了 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++ 标准库接口,未使用第三方题面或测试文件。