[LeetCode] 1792. Maximum Average Pass Ratio

There is a school that has classes of students and each class will be having a final exam. You are given a 2D integer array classes, where classes[i] = [passi, totali]. You know beforehand that in the ith class, there are totali total students, but only passi number of students will pass the exam.

You are also given an integer extraStudents. There are another extraStudents brilliant students that are guaranteed to pass the exam of any class they are assigned to. You want to assign each of the extraStudents students to a class in a way that maximizes the average pass ratio across all the classes.

The pass ratio of a class is equal to the number of students of the class that will pass the exam divided by the total number of students of the class. The average pass ratio is the sum of pass ratios of all the classes divided by the number of the classes.

Return the maximum possible average pass ratio after assigning the extraStudents students. Answers within 10-5 of the actual answer will be accepted.

Example 1:
Input: classes = [[1,2],[3,5],[2,2]], extraStudents = 2
Output: 0.78333
Explanation: You can assign the two extra students to the first class. The average pass ratio will be equal to (3/4 + 3/5 + 2/2) / 3 = 0.78333.

Example 2:
Input: classes = [[2,4],[3,9],[4,5],[2,10]], extraStudents = 4
Output: 0.53485

Constraints:
1 <= classes.length <= 105
classes[i].length == 2
1 <= passi <= totali <= 105
1 <= extraStudents <= 105

最大平均通过率。

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

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

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

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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/maximum-average-pass-ratio
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

思路是贪心，需要用到优先队列。

这个题的题意有点绕，需要细心。注意 code signature 最后要你返回的是 double 所以需要注意精度问题。同时注意题目的细节，因为 extraStudents 是一些一定会通过考试的学生，所以为了提高平均通过率，我们找的不应该是通过率最低的班级，而是找那些加入 extraStudents 之后，通过率提升/变化最多的班级。所以这里我们需要的是一个最大堆。我们将每个班的数据都放到堆中，按照通过率变化由大到小排序，这样，通过率提升最多的班级会在堆顶。

这里我解释一下为什么是找那些加入 extraStudents 之后，通过率提升/变化最多的班级。我参考了这个帖子。注意里面的提示三，在不断地给同一个班级安排学生的过程中，增加的通过率是逐渐单调递减的。

举个例子，如果 x = 3, y = 4，那么 x / y = 3/4（四分之三）。
x + 1 = 4, y + 1 = 5, 那么 x + 1 / y + 1 = 4/5（五分之四）。
x + 2 = 5, y + 2 = 6, 那么 x + 2 / y + 2 = 5/6（六分之五）。
从 3/4 到 4/5 的差距是比 4/5 到 5/6 的差距要大的。这里可以拿笔算一下。所以这里我们把通过率变化最大的元素放在堆顶，每次拿出堆顶元素，从 extraStudents 中拿一个加到堆顶元素，这样一直做直到用完 extraStudents。

复杂度

时间O(nlogn)
空间O(n)

代码

Java实现

class Solution {
    public double maxAverageRatio(int[][] classes, int extraStudents) {
        int n = classes.length;
        // max heap
        PriorityQueue<double[]> queue = new PriorityQueue<>((a, b) -> {
            double x = (b[0] + 1) / (b[1] + 1) - b[0] / b[1];
            double y = (a[0] + 1) / (a[1] + 1) - a[0] / a[1];
            if (x > y) {
                return 1;
            } else if (x < y) {
                return -1;
            }
            return 0;
        });

        for (int[] c : classes) {
            queue.offer(new double[] { c[0], c[1] });
        }

        while (extraStudents > 0) {
            double[] cur = queue.poll();
            cur[0] += 1.0;
            cur[1] += 1.0;
            queue.offer(cur);
            extraStudents--;
        }

        double res = 0;
        while (!queue.isEmpty()) {
            double[] cur = queue.poll();
            res += cur[0] / cur[1];
        }
        return res / n;
    }
}