【二分4】塔子哥的数对问题

题解

题面分析

给定一个长度为 $n$ 的整数数组 $A$ 和一个整数 $C$，需要计算所有满足条件 $A[i] - A[j] = C$ 的数对 $(i, j)$ 的个数，其中 $i$ 和 $j$ 为数组中不同的位置索引。需要注意的是，如果数组中存在重复的元素，即使数值相同但位置不同，也应视为不同的数对。

思路

题目描述：

给定一个整数数组$A$和一个整数$C$，要求计算出所有满足$A[i] - A[j] = C$的数对 $(i, j)$的个数，其中$i$和$j$为数组中的不同位置索引。注意，若$A[i]$和$A[j]$的值相同，但位置不同，则算作不同的数对。

输入：

• 第一行输入一个整数 $n$（$1 \leq n \leq 10^5$），表示数组 $A$ 的大小。
• 第二行输入 $n$ 个整数，表示数组 $A$ 的元素 $A[1], A[2], \ldots, A[n]$（$1 \leq A[i] \leq 10^9$）。
• 第三行输入一个整数 $C$（$1 \leq C \leq 10^9$）。

输出：

输出一个整数，表示满足条件的数对 $(i, j)$ 的个数。

样例输入：

6
1 2 2 3 4 5
2

样例输出：

4

说明：

在上述样例中，满足 $A[i] - A[j] = 2$ 的数对为：

• $(1, 4)$ 对应 $(3 - 1 = 2)$
• $(2, 5)$ 对应 $(4 - 2 = 2)$
• $(3, 5)$ 对应 $(4 - 2 = 2)$
• $(4, 6)$ 对应 $(5 - 3 = 2)$

因此，总数对个数为 4。