用 Python 计算不开心的朋友数量的程序
假设我们有n(even)不同朋友的偏好列表。对于每个人i,preferences[i]包含一个按偏好顺序排序的朋友列表。因此,列表中较早的朋友比列表中较晚的朋友更受欢迎。每个列表中的朋友都按从0到n-1的整数编号。所有的朋友被分成不同的对。其中pairs[i]=[xi,yi]表示xi与yi配对和/或yi与xi配对。但是,如果x与y配对并且存在一个也与v配对的朋友u,则朋友x不高兴,但是-
x比y更喜欢u,并且
你更喜欢x而不是v。
我们必须找到不开心的朋友的数量。
因此,如果输入类似于首选项=[[1,2,3],[3,2,0],[3,1,0],[1,2,0]]对=[[0,1],[2,3]],那么输出将是2因为第一个朋友不开心,因为人1与人0配对但更喜欢人3而不是人0,人3更喜欢人1而不是人2。朋友3不快乐因为第3个人与第2个人配对,但更喜欢第1个人而不是第2个人,第1个人更喜欢第3个人而不是第0个人。
示例
让我们看看以下实现以获得更好的理解-
from collections import defaultdict def solve(preferences, pairs): graph = defaultdict(dict) for start, end in pairs: for pref in preferences[start]: if pref == end: break graph[start][pref] = 1 for pref in preferences[end]: if pref == start: break graph[end][pref] = 1 unhappy = 0 for start, end in pairs: for pref in graph[start]: if graph[pref].get(start, None): unhappy += 1 break for pref in graph[end]: if graph[pref].get(end, None): unhappy += 1 break return unhappy preferences = [[1, 2, 3], [3, 2, 0], [3, 1, 0], [1, 2, 0]] pairs = [[0, 1], [2, 3]] print(solve(preferences, pairs))
输入
[[1, 2, 3], [3, 2, 0], [3, 1, 0], [1, 2, 0]], [[0, 1], [2, 3]]输出结果
2