优先队列与考试

这次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 。

题解

首先，「最大化平均通过率」等价于「最大化总通过率」。

设某个班级的人数为

，其中可以通过考试的人数为

。如果给这个班级安排一个额外的学生，那么该班级的通过率会增加：

在不断地给同一个班级安排学生的过程中，增加的通过率是逐渐单调递减的，即：

每次选择那个可以使得通过率的增加量最大的班级放入一名学生。

思路与算法

令

表示通过率的增加量。我们将

这一三元组放入优先队列（大根堆）中，随后进行

次操作。

每一次操作中，我们取出优先队列的堆顶元素，其对应着当前通过率的增加量最大的班级。我们将一名学生放入该班级，并将

放回优先队列。

最终我们可以得到「最大的总通过率增加量」，加上初始的总通过率后再除以班级数量即可得到答案。

代码

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();
    }
};