这次leetcode周赛第三题是一个求平均值的问题，暴力解法容易超时，比较好的做法是通过优先级队列来实现每次的选择，使得复杂度降为
，是一道很不错的优先级队列问题，在这里分享一下。
题目
一所学校里有一些班级，每个班级里有一些学生，现在每个班都会进行一场期末考试。给你一个二维数组 classes ，其中 classes[i] = [passi, totali] ，表示你提前知道了第 i 个班级总共有 totali 个学生，其中只有 passi 个学生可以通过考试。
给你一个整数 extraStudents ，表示额外有 extraStudents 个聪明的学生，他们 一定 能通过任何班级的期末考。你需要给这 extraStudents 个学生每人都安排一个班级，使得 所有 班级的 平均 通过率 最大 。
一个班级的 通过率 等于这个班级通过考试的学生人数除以这个班级的总人数。平均通过率 是所有班级的通过率之和除以班级数目。
请你返回在安排这 extraStudents 个学生去对应班级后的 最大 平均通过率。与标准答案误差范围在 10-5 以内的结果都会视为正确结果。
示例：
输入：classes = [[1,2],[3,5],[2,2]], extraStudents = 2 输出：0.78333 解释：你可以将额外的两个学生都安排到第一个班级，平均通过率为 (3/4 3/5 2/2) / 3 = 0.78333 。
题解
首先，「最大化平均通过率」等价于「最大化总通过率」。
设某个班级的人数为
，其中可以通过考试的人数为
。如果给这个班级安排一个额外的学生，那么该班级的通过率会增加：
在不断地给同一个班级安排学生的过程中，增加的通过率是逐渐单调递减的，即：
每次选择那个可以使得通过率的增加量最大的班级放入一名学生。
思路与算法
令
表示通过率的增加量。我们将
这一三元组放入优先队列（大根堆）中，随后进行
次操作。
每一次操作中，我们取出优先队列的堆顶元素，其对应着当前通过率的增加量最大的班级。我们将一名学生放入该班级，并将
放回优先队列。
最终我们可以得到「最大的总通过率增加量」，加上初始的总通过率后再除以班级数量即可得到答案。
代码
代码语言：javascript复制class Solution {
public:
double maxAverageRatio(vector<vector<int>>& classes, int extraStudents) {
priority_queue<tuple<double, int, int>> q;
auto diff = [](int x, int y) -> double {
return (double)(x 1) / (y 1) - (double)x / y;
};
double ans = 0.;
for (const auto& c: classes) {
int x = c[0], y = c[1];
ans = (double)x / y;
q.emplace(diff(x, y), x, y);
}
for (int _ = 0; _ < extraStudents; _) {
auto [d, x, y] = q.top();
q.pop();
ans = d;
q.emplace(diff(x 1, y 1), x 1, y 1);
}
return ans / classes.size();
}
};
