题目描述:
给定一个整数数组A和一个整数C,要求计算出所有满足A[i]−A[j]=C的数对 (i,j)的个数,其中i和j为数组中的不同位置索引。注意,若A[i]和A[j]的值相同,但位置不同,则算作不同的数对。
输入:
输出:
输出一个整数,表示满足条件的数对 (i,j) 的个数。
样例输入:
6
1 2 2 3 4 5
2
样例输出:
4
说明:
在上述样例中,满足 A[i]−A[j]=2 的数对为:
因此,总数对个数为 4。
给定一个长度为 n
的整数数组 A
和一个整数 C
,需要计算所有满足条件 A[i] - A[j] = C
的数对 (i, j)
的个数,其中 i
和 j
为数组中不同的位置索引。需要注意的是,如果数组中存在重复的元素,即使数值相同但位置不同,也应视为不同的数对。
我们来分析公式 A[i] - A[j] = C
,变形一下就是 A[i] = A[j] + C
,也就是我们需要找到所有满足 A[i] = A[j] + C
的数对。
首先,我们可以先对数组排序,然后遍历一遍数组,对于每一个 A[j]
,因为我们已经对数组排序了,那么 A[j] + C
的位置一定在 A[j]
的后面,这个数记为 A[i]
,那么此时恰好满足 A[i] - A[j] = C
。
由于已经对数组排序了,且数组中相同的数会堆在一起,所以我们只需要找到 A[j] + C
第一次出现的位置和最后一次出现的位置即可。通过二分查找,我们可以快速计算出有多少个这样的数。问题就转化成了【二分2】的问题。
for a in A:
target = a + C # 计算目标值 x = A[i] + C
# 使用 bisect 查找目标值的出现次数
# bisect_left 返回第一个不小于 target 的位置
# bisect_right 返回第一个大于 target 的位置
count = bisect.bisect_right(A, target) - bisect.bisect_left(A, target)
# 累加数对的数量
sum_pairs += count
import bisect
def count_pairs(A, C):
# 排序数组 A
A.sort()
# 记录数对总数
sum_pairs = 0
# 遍历数组中的每个元素
for a in A:
target = a + C # 计算目标值 x = A[i] + C
# 使用 bisect 查找目标值的出现次数
# bisect_left 返回第一个不小于 target 的位置
# bisect_right 返回第一个大于 target 的位置
count = bisect.bisect_right(A, target) - bisect.bisect_left(A, target)
# 累加数对的数量
sum_pairs += count
return sum_pairs
def main():
# 输入处理
n = int(input()) # 输入数组的大小 n
A = list(map(int, input().split())) # 输入数组 A 的元素
C = int(input()) # 输入整数 C
# 计算并输出结果
result = count_pairs(A, C)
print(result)
if __name__ == "__main__":
main()