求用Python教授的最少人数计算项目
假设我们有一个数字n,一个称为“languages”的数组和一个称为“friendships”的数组,因此有从1到n编号的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,因为我们需要向用户1和3培训语言3,由于有两个用户需要教授,因此输出为2。
要解决此问题,我们将按照以下步骤进行 –
- lang:所有用户所知道的所有不同语言集的列表
- not_comm:一个新集合
- 对于friendships中的每一对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