在 Python 中查找最大平均通过率的程序

假设我们有一个班级列表，其中 classes[i] 代表 [pass_i, total_i] 分别表示通过第 i 个班级考试的学生人数和第 i 个班级的学生总数。我们还有另一个额外的价值。这表明有额外数量的优秀学生保证通过分配给他们的任何班级的考试。我们必须以最大化所有班级平均通过学生人数的方式将每个额外的学生分配到一个班级。一个班级的通过率由将通过的班级学生人数除以该班级学生总数确定。平均通过率是所有类的通过率之和除以类数。在分配额外的学生后，我们必须找到最大可能的平均通过率。

因此，如果输入类似于 classes = [[2,3],[4,6],[3,3]], extra = 3，那么输出将是 0.83809，因为第一堂课多出两个学生并添加一个额外的学生与二等班的比例最大化，所以现在平均值是 (4/5 + 5/7 + 3/3)/3 = 0.83809。

示例

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

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