Python程序计算不满友人人数

假设我们有一个n(偶数)个不同朋友的偏好列表。对于每个人i，偏好[i] 持有已按偏好排序的朋友列表。因此，在列表中较早的朋友比列表中较晚的朋友更受欢迎。每个列表中的朋友按整数0到n-1进行编号。所有的朋友被分成不同的对。其中pairs[i] = [xi, yi] 表示xi 和yi 相配对和/或yi和xi相匹配。但是，如果x与y配对，存在一个友人u也与v配对但 –

• x 更喜欢u而不是y, 和
• u 更喜欢x而不是v。

我们必须找到不满意朋友的数量。

所以，如果输入如下：preferences = [[1, 2, 3], [3, 2, 0], [3, 1, 0], [1, 2, 0]] pairs = [[0, 1], [2, 3]], 那么输出将是2，因为第一个朋友不高兴是因为人1与人0配对，但是喜欢人3而不是人0，人3喜欢人1而不是人2。朋友3很不高兴是因为人3与人2配对，但是喜欢人1而不是人2，人1喜欢人3而不是人0。

要解决此问题，我们将遵循以下步骤−

• 图形:= 空的邻接列表以制作图形
• 对于每个对(s, e)中的(pair)，执行以下操作
  • 对于偏好[s]中的每个pref，执行以下操作
    • 如果pref与end相同，则
    • 退出循环
    • 图[s， pref] := 1
  • 对于偏好 [e]中的每个pref，执行以下操作
    • 如果 pref 与 start 相同，则
    • 退出循环
    • 图[ e ， pref ] := 1
• 不满的 := 0
• 对于(pairs)中的每个对(s, e)，执行以下操作
  • 对于图[s]中的每个pref，执行以下操作
    • 如果图[pref][s]不为空，则
    • 不快乐 := 不快乐 + 1
    • 退出循环
  • 对于[(end)]中的每个pref，执行以下操作
    • 如果图[pref][e]不为空，则
    • 不满意 := 不满意 + 1
    • 退出循环
• 返回不满意

例子

让我们看一下以下实现，以更好地理解−

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