题目描述

一所学校里有一些班级，每个班级里有一些学生，现在每个班都会进行一场期末考试。给你一个二维数组 classes，其中 classes[i] = [pass_i, total_i]，表示你提前知道了第 i 个班级总共有 total_i 个学生，其中只有 pass_i 个学生可以通过考试。

给你一个整数 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 。

输入：classes = [[2,4],[3,9],[4,5],[2,10]], extraStudents = 4
输出：0.53485

限制

• 1 <= classes.length <= 10^5
• classes[i].length == 2
• 1 <= pass_i <= total_i <= 10^5
• 1 <= extraStudents <= 10^5

算法

(贪心) $O((n + m) \log n)$

1. 每个班级的贡献都是独立的，故需要尽可能的先补齐有“潜力”的班级。
2. 容易发现，对于通过率不是 100% 的班级，每添加一名聪明的学生，其通过率一定会上升，但上升的幅度会随着添加的学生个数增多而下降。
3. 所以，对于一名聪明的学生，需要放到当前通过率上升幅度最大的班级中。对每一名学生都这样操作，可以得到最终最大的平均通过率。
4. 采用大根堆（优先队列），根据通过率上升的幅度排序。
5. 每次弹出“潜力”最大的班级，更新后放回堆中。

时间复杂度

• 暴力初始化优先队列的时间复杂度为 $O(n \log n)$。
• 对于每个聪明的学生，需要 $O(\log n)$ 的时间去调整优先队列，故总时间复杂度为 $O((n + m) \log n)$。

空间复杂度

• 需要 $O(n)$ 的空间存储优先队列。

C++ 代码

struct Class {
    int idx, paas, total;
    Class(int idx_, int paas_, int total_):idx(idx_),paas(paas_),total(total_){}

    bool operator < (const Class &o) const {
        return 1.0 * (paas + 1) / (total + 1) - 1.0 * paas / total <
            1.0 * (o.paas + 1) / (o.total + 1) - 1.0 * o.paas / o.total;
    }
};

class Solution {
public:
    double maxAverageRatio(vector<vector<int>>& classes, int extraStudents) {
        const int n = classes.size();
        priority_queue<Class> heap;

        for (int i = 0; i < n; i++)
            heap.push(Class(i, classes[i][0], classes[i][1]));

        while (extraStudents--) {
            Class u = heap.top();
            heap.pop();
            classes[u.idx][0]++;
            classes[u.idx][1]++;
            heap.push(Class(u.idx, u.paas + 1, u.total + 1));
        }

        double ans = 0;
        for (const auto &c : classes)
            ans += 1.0 * c[0] / c[1];
        return ans / n;
    }
};