最大平均通过率【LC1792】
一所学校里有一些班级，每个班级里有一些学生，现在每个班都会进行一场期末考试。给你一个二维数组
classes，其中classes[i] = [passi, totali]，表示你提前知道了第i个班级总共有totali个学生，其中只有passi个学生可以通过考试。给你一个整数
extraStudents，表示额外有extraStudents个聪明的学生，他们 一定 能通过任何班级的期末考。你需要给这extraStudents个学生每人都安排一个班级，使得 所有 班级的 平均 通过率 最大 。
一个班级的 通过率 等于这个班级通过考试的学生人数除以这个班级的总人数。平均通过率 是所有班级的通过率之和除以班级数目。
请你返回在安排这 extraStudents 个学生去对应班级后的 最大 平均通过率。与标准答案误差范围在 10-5 以内的结果都会视为正确结果。
- 思路：
- 首先添加每一个学生时，应使通过率的变化值最大，才能获得最大的平均通过率
- 实现时可以使用大顶堆存储一个二元组，内容各个班级的通过学生和总学生，堆以增加一个通过学生后，通过率的变化值从大到小排序。
- 这样堆顶元素即为添加一个学生通过率变化最大值对应的班级，操作
extraStudents次，然后求得最终的平均通过率返回即可
- 实现
class Solution { public double maxAverageRatio(int[][] classes, int extraStudents) { PriorityQueue<double[]> pq = new PriorityQueue<double[]>((o1, o2) -> (o2[0] + 1) / (o2[1] + 1) - o2[0] / o2[1] > (o1[0] + 1) / (o1[1] + 1) - o1[0] / o1[1] ? 1 : -1 ); for (int[] c : classes){ pq.add(new double[]{c[0], c[1]}); } for (int i = 0; i < extraStudents; i++){ double[] c = pq.poll(); pq.add(new double[]{c[0] + 1, c[1] + 1}); } double res = 0; while (!pq.isEmpty()){ double[] c = pq.poll(); res += c[0] / c[1]; } return res / classes.length; } }
复杂度
- 时间复杂度：O(n+klogn)，n 为班级数量，k 为必通过的学生人数，向堆中添加元素的时间复杂度为O ( l o g n )
- 空间复杂度：O ( n ) ，小顶堆的空间复杂度为O ( n )
