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

假设我们有一个班级列表，其中 classes[i] 表示 [pass_i, total_i]，表示第 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) 元组的列表
堆化 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))