用 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