1792. 最大平均通过率Java

文章发布较早，内容可能过时，阅读注意甄别。

# 题目

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

提示：

1 <= classes.length <= 10⁵
classes[i].length == 2
1 <= passi <= totali <= 10⁵
1 <= extraStudents <= 10⁵

# 思路

贪心策略 + 堆，谁的通过率增加更多，就越排到堆顶：

1.堆排序, 规则是当前班级分子、分母+1后算新的通过率，谁的通过率增加更多，就越排到堆顶；

2.时间复杂度：while循环O(n), 堆的添加时间复杂度O(logn)，总共O(nlogn)。

# 解法

class Solution {
    public double maxAverageRatio(int[][] classes, int extraStudents) {
        if (classes == null) {
            return 0;
        }

        PriorityQueue<int[]> heap = new PriorityQueue<>(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                double avg1 = (o1[0] + 0.0) / o1[1];
                double avg2 = (o2[0] + 0.0) / o2[1];

                double avg1_add = (o1[0] + 1.0) / (o1[1] + 1.0);
                double avg2_add = (o2[0] + 1.0) / (o2[1] + 1.0);

                double res = Double.compare(avg1_add - avg1, avg2_add - avg2);
                if (res > 0) {
                    return -1;
                } else {
                    return 1;
                }
            }
        });

        Collections.addAll(heap, classes);

        while (extraStudents > 0) {
            int[] cls = heap.poll();
            cls[0] = cls[0] + 1;
            cls[1] = cls[1] + 1;
            extraStudents--;
            heap.add(cls);
        }
        double sum = 0;
        while (!heap.isEmpty()) {
            int[] arr = heap.poll();
            sum = sum + (arr[0] + 0.0) / arr[1];
        }
        return sum / classes.length;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

# 总结

分析出几种情况，然后分别对各个情况实现

#Java