用 Python 编写程序，找出最少需要授课的人数
pythonserver side programmingprogramming更新于 2025/12/9 16:44:17
假设我们有一个数字 n、一个名为"languages"的数组和一个名为"friendships"的数组，因此有 n 种语言，编号从 1 到 n，languages[i] 表示第 i 个用户知道的一组语言，friendships[i] 包含一对 [ui, vi]，表示用户 ui 和 vi 之间的友谊。我们可以选择一种语言并将其教给一些用户，以便所有朋友都可以相互交流。我们必须找出教学所需的最少用户数量。 (我们必须记住的一件事是，友谊不是传递性的，所以如果 x 是 y 的朋友，而 y 是 z 的朋友，这并不意味着 x 是 z 的朋友)。
因此，如果输入为 n = 3 languages = [[2],[1,3],[1,2],[3]] friendships = [[1,4],[1,2],[3,4],[2,3]]，则输出将为 2，因为我们需要将语言 3 训练给用户 1 和 3，因为有两个用户需要教，所以输出为 2。
为了解决这个问题，我们将遵循以下步骤 −
- lang := 用户所知的所有不同语言集的列表
- not_comm := 一个新的集合
- 对于友谊中的每一对 a、b，执行
- a := a - 1
- b := b - 1
- 如果 lang[a] 和 lang[b] 不相交，则
- 将 a 插入 not_comm
- 将 b 插入 not_comm
- 如果 not_comm 为空，则
- 返回 0
- cnt := 一个空映射
- 对于 not_comm 中的每个人，执行
- 存储 lang[person] 的频率并将其存储到 cnt
- temp := cnt 所有值列表中的最大值
- 返回 not_comm 的大小 - temp
示例
让我们看看下面的实现以便更好地理解 −
from collections import Counter def solve(n, languages, friendships): lang = [set(L) for L in languages] not_comm = set() for a,b in friendships: a -= 1 b -= 1 if lang[a].isdisjoint(lang[b]): not_comm.add(a) not_comm.add(b) if not not_comm: return 0 cnt = Counter() for person in not_comm: cnt.update(lang[person]) temp = max(cnt.values()) return len(not_comm) - temp n = 3 languages = [[2],[1,3],[1,2],[3]] friendships = [[1,4],[1,2],[3,4],[2,3]] print(solve(n, languages, friendships))
输入
3, [[2],[1,3],[1,2],[3]], [[1,4],[1,2],[3,4],[2,3]]
输出
2
相关文章
有用资源
python 参考教程 - 该教程包含有关 python 的更多信息:https://www.cainiaomax.com/python/
