2023年华为OD机试（python）B卷-符合要求的结对方式

一、题目

题目描述：

用一个数组A代表程序员的工作能力，公司想通过结对编程的方式提高员工的能力，假设结对后的能力为两个员工的能力之和，求一共有多少种结对方式使结对后能力为N。

二、输入输出

输入描述:
5
1 2 2 2 3
4
第一行为员工的总人数，取值范围[1,1000]
第二行为数组A的元素，每个元素的取值范围[1,1000]
第三行为N的值，取值范围[1,1000]
输出描述:
4
满足结对后能力为N的结对方式总数。

三、示例

示例1?

输入输出示例仅供调试，后台判题数据一般不包含示例
输入:
5
1 2 2 2 3
4
输出:
4
说明:
满足要求的结对方式为：A[0]和A[4]，A[1]和A[2]，A[1]和A[3]，A[2]和A[3]。

四、要求

时间限制：C/C++ 1秒，其他语言 2秒
空间限制：C/C++262144K，其他语言524288K

五、解题思路

1. 首先，我们需要统计数组arr中每个元素的出现次数，可以使用一个字典freq来实现，其中字典的键是元素的值，字典的值是元素的出现次数。
2. 然后，我们遍历数组arr中的每个元素num，对于每个元素，我们计算与之配对后的能力值complement，即target - num。
3. 如果complement存在于字典freq中，说明存在一种配对方式使得两个员工的能力之和为target。此时，我们将字典freq中complement对应的值加到计数器count上。
4. 注意，如果complement与num相等，说明当前元素可以与自己配对，但是每个元素只能被计数一次，所以需要将计数器count减去1。
5. 最后，结对方式总数为计数器count除以2（因为每对结对方式会被计算两次）。
6. 返回计数器count作为结果，即满足结对后能力为target的结对方式总数。

六、参考代码?

# -*- coding: utf-8 -*-
'''
@File    :   2023-B-符合要求的结对方式.py
@Time    :   2023/12/28 00:56:22
@Author  :   mgc 
@Version :   1.0
@Desc    :   None
'''

def countPairings(n, arr, target):
    count = 0  # 计数器，用于记录满足结对后能力为target的结对方式总数

    # 创建一个字典，用于统计数组arr中每个元素的出现次数
    freq = {}
    for num in arr:
        freq[num] = freq.get(num, 0) + 1

    # 遍历数组arr中的每个元素
    for num in arr:
        complement = target - num  # 计算与当前元素配对后的能力值

        # 如果配对的能力值存在于数组arr中
        if complement in freq:
            count += freq[complement]  # 更新计数器，增加配对方式的数量

            # 如果配对的能力值与当前元素相等，需要将当前元素的出现次数减一
            if complement == num:
                count -= 1

    # 结对方式总数为计数器count除以2（因为每对结对方式会被计算两次）
    return count // 2


# 测试代码
n = int(input())  # 员工的总人数
arr = list(map(int, input().split()))  # 数组A的元素
target = int(input())  # 目标能力值N

result = countPairings(n, arr, target)
print(result)