用 Python 编写程序来查找最大平均通过率

pythonserver side programmingprogramming更新于 2025/12/2 11:24:17

假设我们有一个班级列表，其中 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 := 类中每对 (a, b) 的元组列表，如 (a/b-(a + 1)/(b + 1), a, b)
heapify 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))