LeetCode 1792 最大平均通过率

题目链接

一所学校里有一些班级，每个班级里有一些学生，现在每个班都会进行一场期末考试。给你一个二维数组 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

一开始想的是排序，后来发现变化是动态的，观察到 extraStudents 这个变量不大，那可以就用优先队列一个一个加，我们优先队列存每个班加一个学生之后提升的通过率，设为大根堆，每次对队头操作即可，AC 代码如下：

class Solution {
public:
    double maxAverageRatio(vector<vector<int>> &classes, int extraStudents) {
        priority_queue<tuple<double, int, int>, vector<tuple<double, int, int>>, less<>> q;
        double sum = 0;
        for (auto &i:classes)
            sum += double(i[0]) / i[1], q.push({double(i[0] + 1) / (i[1] + 1) - double(i[0]) / i[1], i[0], i[1]});
        while (extraStudents) {
            extraStudents--;
            auto[a, b, c]=q.top();
            q.pop();
            sum += a;
            q.push({double(b + 2) / (c + 2) - double(b + 1) / (c + 1), b + 1, c + 1});
        }
        return sum / classes.size();
    }
};