LeetCode 1792中等堆 · 优先队列
最大平均通过率 图解题解
这道题到底在问什么
看清楚:平均通过率 = 每个班比率之和 ÷ 班级数,班级数是固定的,所以只要让「比率之和」尽量大就行。一名额外学生进哪个班,会让那个班从 pass/total 变成 (pass+1)/(total+1),比率往上抬一点。问题是有好几名学生、好几个班,每人该进哪个班?注意一个班可以进不止一名学生。演示里 4 个班的初始比率分别是 0.500、0.600、0.500、1.000,平均 0.650,我们要把 3 名学生安排到位,把这个平均顶到最大。
- 输入
- classes=[[1,2],[3,5],[2,2]], extra=2
- 输出
- 0.78333
- 输入
- classes=[[2,2]], extra=1
- 输出
- 1.00000
- 输入
- classes=[[1,2],[2,2]], extra=1
- 输出
- 0.83333
最优解：一步一步想明白
- 3记牢:每名学生给「增益最大」的班,增益 = (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。
- 5看 A 班 [1,2]。它现在比率 0.500,如果分一名学生进去就变成 [2,3],比率 0.667,往上抬了 0.167。这个抬升 +0.167 就是 A 班当前的增益。
- 6看 B 班 [3,5]。它现在比率 0.600,如果分一名学生进去就变成 [4,6],比率 0.667,往上抬了 0.067。这个抬升 +0.067 就是 B 班当前的增益。
- 7看 C 班 [2,4]。它现在比率 0.500,如果分一名学生进去就变成 [3,5],比率 0.600,往上抬了 0.100。这个抬升 +0.100 就是 C 班当前的增益。
- 8看 D 班 [2,2]。它现在比率 1.000,如果分一名学生进去就变成 [3,3],比率 1.000,往上抬了 0.000。这个抬升 +0.000 就是 D 班当前的增益。D 班本来就 2/2 满通过率了,再加人还是满,增益是 0,自然排最后。
- 9把 4 个班按增益从大到小建成一个大顶堆,增益最大的浮到堆顶。现在堆顶是 A 班,增益 +0.167,是四个里最大的。接下来每来一名学生,就弹堆顶给它。
- 10第 1 名学生来了。看堆顶,是 A 班,增益 +0.167,在所有班里最大,所以这一名学生就分给 A 班,它的比率能抬得最多。把堆顶弹出来准备处理。
- 11把学生加进 A 班,它从 [1,2] 变成 [2,3],比率从 0.500 升到 0.667。这一步实实在在把这个班的通过率抬上去了。它是刚弹出正在处理的班,增益还没重算,先不算堆顶,下一帧压回堆再定新堆顶。
- 12关键一步:A 班加了人,它的增益从 +0.167 掉到 +0.083,因为同一个班越加、每次能抬的越少。把它带着新增益压回堆,堆重新调整,现在堆顶是 C 班,增益 +0.100。注意堆顶换人了,下一名学生会去 C 班。还剩 2 名。
- 13第 2 名学生来了。看堆顶,是 C 班,增益 +0.100,在所有班里最大,所以这一名学生就分给 C 班,它的比率能抬得最多。把堆顶弹出来准备处理。
- 14把学生加进 C 班,它从 [2,4] 变成 [3,5],比率从 0.500 升到 0.600。这一步实实在在把这个班的通过率抬上去了。它是刚弹出正在处理的班,增益还没重算,先不算堆顶,下一帧压回堆再定新堆顶。
- 15关键一步:C 班加了人,它的增益从 +0.100 掉到 +0.067,因为同一个班越加、每次能抬的越少。把它带着新增益压回堆,堆重新调整,现在堆顶是 A 班,增益 +0.083。注意堆顶换人了,下一名学生会去 A 班。还剩 1 名。
- 16第 3 名学生来了。看堆顶,是 A 班,增益 +0.083,在所有班里最大,所以这一名学生就分给 A 班,它的比率能抬得最多。把堆顶弹出来准备处理。
- 17把学生加进 A 班,它从 [2,3] 变成 [3,4],比率从 0.667 升到 0.750。这一步实实在在把这个班的通过率抬上去了。它是刚弹出正在处理的班,增益还没重算,先不算堆顶,下一帧压回堆再定新堆顶。
- 18关键一步:A 班加了人,它的增益从 +0.083 掉到 +0.050,因为同一个班越加、每次能抬的越少。把它带着新增益压回堆,堆重新调整,现在堆顶是 B 班,增益 +0.067。不过 3 名学生已经用完,重算后堆顶更新为 B 班,只是让堆保持正确,不再分配学生。
- 193 名学生都安排好了,回头看四个班现在的比率:B 班 0.600、C 班 0.600、A 班 0.750、D 班 1.000。最后一步就是把这四个比率加起来除以 4,得到平均通过率。
- 20把 B 班的比率 0.600 加进来,比率和先记 0.600。继续加下一个班。
- 21把 C 班的比率 0.600 加进来,比率和从 0.600 变成 1.200。继续加下一个班。
- 22把 A 班的比率 0.750 加进来,比率和从 1.200 变成 1.950。继续加下一个班。
- 23把 D 班的比率 1.000 加进来,比率和从 1.950 变成 2.950。四个班加完了,总和 2.950。
- 24比率之和 2.950 除以班级数 4,得到 0.7375。这就是把 3 名学生贪心地按增益分配后能拿到的最大平均通过率,和开头说的答案对上了。
- 25回看全程:每名学生都给了当时增益最大的班。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。
⚠️ 容易写错的地方
✗ 错：按当前比率最低的班来分学生
✓ 对：按增益 (pass+1)/(total+1) 减 pass/total 最大的班来分
比率低不代表加人抬得多。比如 [1,100] 比率很低但加一人只从 0.010 抬到 0.020,几乎没用;而 [1,2] 加一人从 0.5 抬到 0.667,抬升大得多。要看的是「加一人能抬多少」,即增益,不是当前比率高低
✗ 错：把学生一次性全塞给同一个增益最大的班
✓ 对：每分一人就重算这个班的增益再放回堆,下一人重新比较
同一个班越加增益越小(边际递减),塞第二个人时它可能已经不是最大了。演示里 A 班拿完第一人增益从 +0.167 掉到 +0.083,到第二轮 C 班的 +0.100 反超,所以第二名学生该先给 C。必须每步重算重比
✗ 错：用整数算比率,pass/total 直接整除
✓ 对：全程用浮点(double)算比率和增益
pass 小于 total 时整数除会得 0,比率全变成 0,答案彻底错。增益是很小的小数,必须用浮点保留精度,题目也允许 1e-5 的误差
完整代码（Python / C++ / Java）
Python
from __future__ import annotations
from 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 = right
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
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)C++
#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <optional>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
struct ListNode {
int val;
ListNode *next;
ListNode() : val(0), next(nullptr) {}
ListNode(int x) : val(x), next(nullptr) {}
ListNode(int x, ListNode *next) : val(x), next(next) {}
};
class Solution {
public:
double maxAverageRatio(vector<vector<int>>& classes, int extraStudents) {
priority_queue<tuple<double, int, int>> pq;
for (auto& e : classes) {
int a = e[0], b = e[1];
double x = (double) (a + 1) / (b + 1) - (double) a / b;
pq.push({x, a, b});
}
while (extraStudents--) {
auto [_, a, b] = pq.top();
pq.pop();
a++;
b++;
double x = (double) (a + 1) / (b + 1) - (double) a / b;
pq.push({x, a, b});
}
double ans = 0;
while (pq.size()) {
auto [_, a, b] = pq.top();
pq.pop();
ans += (double) a / b;
}
return ans / classes.size();
}
};Java
import java.util.*;
class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(){} TreeNode(int val){this.val=val;} TreeNode(int val, TreeNode left, TreeNode right){this.val=val;this.left=left;this.right=right;} }
class ListNode { int val; ListNode next; ListNode(){} ListNode(int val){this.val=val;} ListNode(int val, ListNode next){this.val=val;this.next=next;} }
class Solution {
public double maxAverageRatio(int[][] classes, int extraStudents) {
PriorityQueue<double[]> pq = new PriorityQueue<>((a, b) -> {
double x = (a[0] + 1) / (a[1] + 1) - a[0] / a[1];
double y = (b[0] + 1) / (b[1] + 1) - b[0] / b[1];
return Double.compare(y, x);
});
for (int[] e : classes) {
pq.offer(new double[] {e[0], e[1]});
}
while (extraStudents-- > 0) {
double[] e = pq.poll();
double a = e[0] + 1, b = e[1] + 1;
pq.offer(new double[] {a, b});
}
double ans = 0;
while (!pq.isEmpty()) {
double[] e = pq.poll();
ans += e[0] / e[1];
}
return ans / classes.length;
}
}复杂度
时间
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),与额外学生数无关(学生是加在已有班上,不新增堆元素)
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 最大平均通过率 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么每一步取增益最大就能保证最终平均最大,贪心的正确性怎么说?+
因为每名学生的分配是独立叠加的,总的比率之和等于各班比率提升的累加,和「先分谁后分谁」无关,只和「每一步各选了多大的提升」有关。每个班的增益随加人只减不增,是边际收益递减的离散凹序列,所以每次把当前可选的最大提升拿走,不会挡住未来更大的提升。任意一步选一个不是最大的增益,都可以换成当前最大的那步而结果不更差,这就说明贪心得到的总和是最大的。
如果不用堆,直接每次线性扫一遍找增益最大的班,复杂度会怎样,什么时候更好?+
线性找最大是 O(n),extra 名学生就是 O(n·extra),加上最后求和 O(n)。当 extra 和 n 都很大时,O(n·extra) 会明显比堆的 O((n+extra) log n) 慢。但如果班级数 n 很小、或 extra 很小,线性写法常数小、实现简单,反而更划算。堆的优势在 n 大、extra 也大的场景,把每次找最大从 O(n) 压到 O(log n)。
增益 (pass+1)/(total+1) 减 pass/total 直接用浮点比较,会不会有精度问题,怎么稳一点?+
一般规模用 double 足够,题目允许 1e-5 误差,浮点误差远小于这个,不会影响堆的比较结果。若想更稳,可以把两个班增益的比较改成通分后比较分子,避免除法,但会牺牲可读性。工程上通常直接用 double,注意的是别用整数除、别在比较里反复重算同一个班的增益(可以把增益缓存进堆元素,像 C++ 和 Python 那样存进 tuple)。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 最大平均通过率 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。