1792.最大平均通过率

问题描述

1792. 最大平均通过率 (Medium)

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

给你一个整数 extraStudents ，表示额外有 extraStudents 个聪明的学生，他们 一定 能通过任何班级的期末考。你需要给这 extraStudents 个学生每人都安排一个班级，使得 所有 班级的 平均 通过率 最大 。

一个班级的 通过率 等于这个班级通过考试的学生人数除以这个班级的总人数。 平均通过率 是所有班级的通过率之和除以班级数目。

请你返回在安排这 extraStudents 个学生去对应班级后的 最大 平均通过率。与标准答案误差范围在 10-⁵ 以内的结果都会视为正确结果。

示例 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

提示：

• 1 <= classes.length <= 10⁵
• classes[i].length == 2
• 1 <= passᵢ <= totalᵢ <= 10⁵
• 1 <= extraStudents <= 10⁵

解题思路

贪心，每次选择使通过率提升最大的那个班级，利用优先队列来模拟这个过程。

代码

class Solution {
  public:
    double maxAverageRatio(vector<vector<int>> &classes, int extraStudents) {
        auto cmp = [&](int a, int b) {
            return (double)(classes[a][1] - classes[a][0]) / ((long long)classes[a][1] * classes[a][1] + classes[a][1]) < (double)(classes[b][1] - classes[b][0]) / ((long long)classes[b][1] * classes[b][1] + classes[b][1]);
        };
        std::priority_queue<int, vector<int>, decltype(cmp)> pq(cmp);
        for (int i = 0; i < classes.size(); i++) {
            pq.push(i);
        }
        for (int num = 1; num <= extraStudents; num++) {
            int idx = pq.top();
            pq.pop();
            classes[idx][0] += 1;
            classes[idx][1] += 1;
            pq.push(idx);
        }
        double res = 0;
        for (auto &vec : classes) {
            res += (double)(vec[0]) / vec[1];
        }
        return res / classes.size();
    }
};