LeetCode 题解工作台
最大平均通过率
一所学校里有一些班级，每个班级里有一些学生，现在每个班都会进行一场期末考试。给你一个二维数组 classes ，其中 classes[i] = [pass i , total i ] ，表示你提前知道了第 i 个班级总共有 total i 个学生，其中只有 pass i 个学生可以通过考试。 给你一…
3
题型
6
代码语言
3
相关题
当前训练重点
中等 · 贪心·invariant
答案摘要
假设一个班级当前的通过率为 ，那么如果我们将一个聪明的学生安排到此班级，那么班级的通过率就会变为 。我们可以发现，通过率的增量为 $\frac{a+1}{b+1} - \frac{a}{b}$。 我们维护一个大根堆，堆中存储的是每个班级的通过率增量。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 贪心·invariant 题型思路
题目描述
一所学校里有一些班级，每个班级里有一些学生，现在每个班都会进行一场期末考试。给你一个二维数组 classes ，其中 classes[i] = [passi, totali] ，表示你提前知道了第 i 个班级总共有 totali 个学生，其中只有 passi 个学生可以通过考试。
给你一个整数 extraStudents ，表示额外有 extraStudents 个聪明的学生，他们 一定 能通过任何班级的期末考。你需要给这 extraStudents 个学生每人都安排一个班级，使得 所有 班级的 平均 通过率 最大 。
一个班级的 通过率 等于这个班级通过考试的学生人数除以这个班级的总人数。平均通过率 是所有班级的通过率之和除以班级数目。
请你返回在安排这 extraStudents 个学生去对应班级后的 最大 平均通过率。与标准答案误差范围在 10-5 以内的结果都会视为正确结果。
示例 1：
输入：classes = [[1,2],[3,5],[2,2]], extraStudents = 2
输出：0.78333
解释：你可以将额外的两个学生都安排到第一个班级，平均通过率为 (3/4 + 3/5 + 2/2) / 3 = 0.78333 。
示例 2：
输入：classes = [[2,4],[3,9],[4,5],[2,10]], extraStudents = 4
输出：0.53485
提示：
1 <= classes.length <= 105classes[i].length == 21 <= passi <= totali <= 1051 <= extraStudents <= 105
解题思路
方法一：优先队列（增量大根堆）
假设一个班级当前的通过率为 ，那么如果我们将一个聪明的学生安排到此班级，那么班级的通过率就会变为 。我们可以发现，通过率的增量为 。
我们维护一个大根堆，堆中存储的是每个班级的通过率增量。
进行 extraStudents 次操作，每次从堆顶取出一个班级，将这个班级的人数和通过人数都加 ，然后将这个班级的通过率增量重新计算并放回堆中。重复这个过程，直到将所有的学生都分配完毕。
最后，我们将所有班级的通过率求和，然后除以班级数目，即为答案。
时间复杂度 ，空间复杂度 。其中 为班级数目。
class Solution:
def maxAverageRatio(self, classes: List[List[int]], extraStudents: int) -> float:
h = [(a / b - (a + 1) / (b + 1), a, b) for a, b in classes]
heapify(h)
for _ in range(extraStudents):
_, a, b = heappop(h)
a, b = a + 1, b + 1
heappush(h, (a / b - (a + 1) / (b + 1), a, b))
return sum(v[1] / v[2] for v in h) / len(classes)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(k \cdot \log(n) + n), where k is extraStudents and n is number of classes due to heap operations for each assignment. Space complexity is O(n) for storing the heap and class states. |
| 空间 | O(n) |
面试官常问的追问
外企场景- question_mark
Look for correct greedy selection by evaluating marginal gain for each class.
- question_mark
Check heap usage for efficient selection of the class with the maximum potential increase.
- question_mark
Ensure correct floating-point handling and avoid integer division errors.
常见陷阱
外企场景- error
Not recalculating the gain after each student assignment can lead to suboptimal choices.
- error
Assigning extra students without using a heap or priority queue may exceed time limits for large inputs.
- error
Ignoring floating-point precision may cause the output to fail strict test cases.
进阶变体
外企场景- arrow_right_alt
Assigning extra students but minimizing the average failure ratio instead of maximizing pass ratio.
- arrow_right_alt
Weighted classes where some classes contribute more to the average, modifying the greedy choice.
- arrow_right_alt
Limited extraStudents per class, requiring a modified heap strategy to respect per-class limits.