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

Arnab Chakraborty

更新于：2021年10月6日

浏览量：143

开启你的职业生涯

完成课程获得认证

开始学习