数据结构
网络
关系数据库管理系统(RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究Python程序：查找最大平均及格率
假设我们有一系列班级，其中classes[i]表示[pass_i, total_i]，分别代表第i个班级的及格学生人数和总学生人数。我们还有一个额外的值extra，它表示保证能通过任何分配给他们的班级考试的优秀学生人数。我们必须将每个额外学生分配到一个班级，以最大化所有班级的平均及格学生人数。班级的及格率由及格学生人数除以总学生人数决定。平均及格率是所有班级的及格率之和除以班级数。我们必须找到分配额外学生后的最大可能的平均及格率。
因此，如果输入类似classes = [[2,3],[4,6],[3,3]]，extra = 3，则输出将为0.83809，因为将两个额外学生分配到第一个班级，并将一个额外学生分配到第二个班级以最大化比率，因此现在的平均值为(4/5 + 5/7 + 3/3)/3 = 0.83809。
为了解决这个问题，我们将遵循以下步骤：
h := 一个元组列表，例如对于classes中的每个对(a, b)，(a/b-(a + 1)/(b + 1), a, b)
heapify h (将h堆化)
当extra不为零时，执行以下操作：
(v, a, b) := h的顶部，并将其从h中删除
(a, b) := (a + 1, b + 1)
将(-(a + 1) /(b + 1) + a / b, a, b)插入堆中
extra := extra - 1
返回h所有元组的平均值
示例
让我们看看下面的实现，以便更好地理解：
import heapq
def solve(classes, extra):
h = [(a / b - (a + 1) / (b + 1), a, b) for a, b in classes]
heapq.heapify(h)
while extra:
v, a, b = heapq.heappop(h)
a, b = a + 1, b + 1
heapq.heappush(h, (-(a + 1) / (b + 1) + a / b, a, b))
extra -= 1
return sum(a / b for v, a, b in h) / len(h)
classes = [[2,3],[4,6],[3,3]]
extra = 3
print(solve(classes, extra))输入
[[2,3],[4,6],[3,3]], 3
输出
0
更新于：2021年10月6日
浏览量：143
广告