题目描述

n 个男生和 n 个女生, 每个男生和与之对应的女生相互吸引, 但选出男女双方都满意的方案时(即两个人的吸引值不同$a_i \neq b_j$), 每个人只有一个合适的对象。

题解

思路:由于男生和女生配对时不能有相同的值，那么我们分值域来考虑。对于男生中的 值=x 的这些人，我们需要匹配女生里的非x值。 匹配方案个数就是 男生中x的个数 乘以 女生中非x的个数。答案就是所有值的方案的和。 为了快速查询女生/男生集合中某个值出现的次数，我们自然想到使用哈希表来统计。

AC代码

• Python

def get_dict(arr):
    dict = {}