用 Python 编写一个程序来计算不开心的朋友数量
pythonserver side programmingprogramming更新于 2025/11/26 10:52:17
假设我们有一个 n(偶数)个不同朋友的偏好列表。对于每个人 i，preferences[i] 保存着一个按偏好顺序排序的朋友列表。因此，列表中较早的朋友比列表中较晚的朋友更受欢迎。每个列表中的朋友都用从 0 到 n-1 的整数编号。所有朋友都被分成不同的对。其中，pairs[i] = [xi, yi] 表示 xi 与 yi 配对和/或 yi 与 xi 配对。但是，如果 x 与 y 配对，并且存在一个朋友 u，他也与 v 配对，但 −，则朋友 x 会不高兴。
- x 更喜欢 u 而不是 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 号人。
为了解决这个问题，我们将遵循以下步骤 −
- graph := 一个邻接列表来制作图表，最初为空
- 对于成对的每对 (s, e)，执行
- 对于 preference[s] 中的每个 pref，执行
- 如果 pref 与 end 相同，则
- 从循环中出来
- graph[s, pref] := 1
- 如果 pref 与 end 相同，则
- 对于 preference[e] 中的每个 pref，执行
- 如果 pref 与 start 相同，则
- 从循环中出来循环
- graph[e, pref] := 1
- 如果 pref 与 start 相同，则
- 对于 preference[s] 中的每个 pref，执行
- unhappy := 0
- 对于成对的每对 (s, e)，执行
- 对于 graph[s] 中的每个 pref，执行
- 如果 graph[pref][s] 不为空，则
- unhappy := unhappy + 1
- 从循环中退出
- 如果 graph[pref][s] 不为空，则
- 对于 graph[end] 中的每个 pref，执行
- 如果 graph[pref][e] 不为空，则
- unhappy := unhappy + 1
- 从循环中退出循环
- 如果 graph[pref][e] 不为空，则
- 对于 graph[s] 中的每个 pref，执行
- 返回 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
相关文章
有用资源
python 参考教程 - 该教程包含有关 python 的更多信息:https://www.cainiaomax.com/python/
