题目描述
思路解析动画文字版
记牢:每名学生给「增益最大」的班,增益 = (pass+1)/(total+1) 减 pass/total;同一个班越加增益越小,所以堆顶会换人。下面用大顶堆一步步分。
总览 · 4 个班的初始通过率：先把 4 个班摆上来,圈里是「通过/总数」,下面小字是它现在的增益,也就是再加一名学生比率能往上抬多少。现在还没排堆,只是把每个班的增益都先算出来:A [1,2] 增益 +0.167,B [3,5] 增益 +0.067,C [2,4] 增益 +0.100,D [2,2] 增益 +0.000。初始平均 0.650。
算增益 · A 班：看 A 班 [1,2]。它现在比率 0.500,如果分一名学生进去就变成 [2,3],比率 0.667,往上抬了 0.167。这个抬升 +0.167 就是 A 班当前的增益。
算增益 · B 班：看 B 班 [3,5]。它现在比率 0.600,如果分一名学生进去就变成 [4,6],比率 0.667,往上抬了 0.067。这个抬升 +0.067 就是 B 班当前的增益。
算增益 · C 班：看 C 班 [2,4]。它现在比率 0.500,如果分一名学生进去就变成 [3,5],比率 0.600,往上抬了 0.100。这个抬升 +0.100 就是 C 班当前的增益。
算增益 · D 班：看 D 班 [2,2]。它现在比率 1.000,如果分一名学生进去就变成 [3,3],比率 1.000,往上抬了 0.000。这个抬升 +0.000 就是 D 班当前的增益。D 班本来就 2/2 满通过率了,再加人还是满,增益是 0,自然排最后。
建大顶堆 · 增益最大的浮到堆顶：把 4 个班按增益从大到小建成一个大顶堆,增益最大的浮到堆顶。现在堆顶是 A 班,增益 +0.167,是四个里最大的。接下来每来一名学生,就弹堆顶给它。
第 1 名学生 · 弹出堆顶：第 1 名学生来了。看堆顶,是 A 班,增益 +0.167,在所有班里最大,所以这一名学生就分给 A 班,它的比率能抬得最多。把堆顶弹出来准备处理。
第 1 名学生 · 加进 A 班：把学生加进 A 班,它从 [1,2] 变成 [2,3],比率从 0.500 升到 0.667。这一步实实在在把这个班的通过率抬上去了。它是刚弹出正在处理的班,增益还没重算,先不算堆顶,下一帧压回堆再定新堆顶。
第 1 名学生 · 重算增益压回堆：关键一步:A 班加了人,它的增益从 +0.167 掉到 +0.083,因为同一个班越加、每次能抬的越少。把它带着新增益压回堆,堆重新调整,现在堆顶是 C 班,增益 +0.100。注意堆顶换人了,下一名学生会去 C 班。还剩 2 名。
第 2 名学生 · 弹出堆顶：第 2 名学生来了。看堆顶,是 C 班,增益 +0.100,在所有班里最大,所以这一名学生就分给 C 班,它的比率能抬得最多。把堆顶弹出来准备处理。
第 2 名学生 · 加进 C 班：把学生加进 C 班,它从 [2,4] 变成 [3,5],比率从 0.500 升到 0.600。这一步实实在在把这个班的通过率抬上去了。它是刚弹出正在处理的班,增益还没重算,先不算堆顶,下一帧压回堆再定新堆顶。
第 2 名学生 · 重算增益压回堆：关键一步:C 班加了人,它的增益从 +0.100 掉到 +0.067,因为同一个班越加、每次能抬的越少。把它带着新增益压回堆,堆重新调整,现在堆顶是 A 班,增益 +0.083。注意堆顶换人了,下一名学生会去 A 班。还剩 1 名。
第 3 名学生 · 弹出堆顶：第 3 名学生来了。看堆顶,是 A 班,增益 +0.083,在所有班里最大,所以这一名学生就分给 A 班,它的比率能抬得最多。把堆顶弹出来准备处理。
第 3 名学生 · 加进 A 班：把学生加进 A 班,它从 [2,3] 变成 [3,4],比率从 0.667 升到 0.750。这一步实实在在把这个班的通过率抬上去了。它是刚弹出正在处理的班,增益还没重算,先不算堆顶,下一帧压回堆再定新堆顶。
第 3 名学生 · 重算增益压回堆：关键一步:A 班加了人,它的增益从 +0.083 掉到 +0.050,因为同一个班越加、每次能抬的越少。把它带着新增益压回堆,堆重新调整,现在堆顶是 B 班,增益 +0.067。不过 3 名学生已经用完,重算后堆顶更新为 B 班,只是让堆保持正确,不再分配学生。
收尾 · 学生分完,开始结算：3 名学生都安排好了,回头看四个班现在的比率:B 班 0.600、C 班 0.600、A 班 0.750、D 班 1.000。最后一步就是把这四个比率加起来除以 4,得到平均通过率。
结算 · 累加 B 班比率：把 B 班的比率 0.600 加进来,比率和先记 0.600。继续加下一个班。
结算 · 累加 C 班比率：把 C 班的比率 0.600 加进来,比率和从 0.600 变成 1.200。继续加下一个班。
结算 · 累加 A 班比率：把 A 班的比率 0.750 加进来,比率和从 1.200 变成 1.950。继续加下一个班。
结算 · 累加 D 班比率：把 D 班的比率 1.000 加进来,比率和从 1.950 变成 2.950。四个班加完了,总和 2.950。
答案 · 平均通过率 0.7375：比率之和 2.950 除以班级数 4,得到 0.7375。这就是把 3 名学生贪心地按增益分配后能拿到的最大平均通过率,和开头说的答案对上了。
完成 · 贪心按增益分配：回看全程:每名学生都给了当时增益最大的班。A 班一开始增益 +0.167 最大,先拿了第一人;加完增益降到 +0.083,被 C 班的 +0.100 反超,第二人就给了 C 班;C 班加完降到 +0.067,A 班又以 +0.083 回到堆顶,第三人再给 A 班。所以分配顺序是 A、C、A,A 班拿 2 人、C 班拿 1 人。就靠「每次挑增益最大、加完重算压回堆」,平均通过率从 0.650 提到了 0.7375。
边界:满率班增益 0 加人无用;1/100000 这种极低比率班加一人增益也极小,比率低不等于增益大;原题示例两人都进 [1,2] 得 0.78333。
面试重点:增益边际递减(离散凹)保证贪心正确;n、extra 都大时堆比线性快;浮点比较在 1e-5 误差内够稳,别整数除。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = rightclass ListNode: def __init__(self, val=0, next=None): self.val = val self.next = nextclass 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)复杂度
- 时间：O((n + extra) log n)，n 是班级数。建堆 O(n);每名额外学生做一次弹堆顶加压回,是 O(log n),共 extra 名,合计 O(extra log n);最后把 n 个班的比率求和是 O(n)。总体 O((n + extra) log n)
- 空间：O(n)，按峰值算,堆里始终装着 n 个班的状态,占 O(n);除此之外只用了固定几个变量。所以额外空间是堆的 O(n),与额外学生数无关(学生是加在已有班上,不新增堆元素)
易错点
面试追问把动画讲成自己的话
追问为什么每一步取增益最大就能保证最终平均最大,贪心的正确性怎么说?
追问如果不用堆,直接每次线性扫一遍找增益最大的班,复杂度会怎样,什么时候更好?
追问增益 (pass+1)/(total+1) 减 pass/total 直接用浮点比较,会不会有精度问题,怎么稳一点?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
最小未被占据椅子的编号
LeetCode 1942 · 中等 · 沿着 堆套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题