Python程序：计算不开心朋友的数量

假设我们有一个包含 n（偶数）个不同朋友的偏好列表。对于每个人 i，preferences[i] 包含一个按偏好顺序排列的朋友列表。因此，列表中较早的朋友比列表中较晚的朋友更受青睐。每个列表中的朋友由整数 0 到 n-1 编号。所有朋友都分成不同的配对。其中 pairs[i] = [xi, yi] 表示 xi 与 yi 配对，反之亦然。但如果朋友 x 与 y 配对，并且存在另一个朋友 u 也与 v 配对，则朋友 x 不开心 -

• 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。

为了解决这个问题，我们将遵循以下步骤 -

• graph := 一个邻接表来创建图，最初为空
• 对于 pairs 中的每个配对 (s, e)，执行以下操作
  • 对于 preferences[s] 中的每个 pref，执行以下操作
    • 如果 pref 与 end 相同，则
      • 退出循环
    • graph[s, pref] := 1
  • 对于 preferences[e] 中的每个 pref，执行以下操作
    • 如果 pref 与 start 相同，则
      • 退出循环
    • graph[e, pref] := 1
• unhappy := 0
• 对于 pairs 中的每个配对 (s, e)，执行以下操作
  • 对于 graph[s] 中的每个 pref，执行以下操作
    • 如果 graph[pref][s] 不为空，则
      • unhappy := unhappy + 1
      • 退出循环
  • 对于 graph[end] 中的每个 pref，执行以下操作
    • 如果 graph[pref][e] 不为空，则
      • unhappy := unhappy + 1
      • 退出循环
• 返回 unhappy

示例

让我们看看以下实现以获得更好的理解 -

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

Arnab Chakraborty

更新于: 2021年10月4日

浏览量 182

开启你的 职业生涯

通过完成课程获得认证

开始学习