【每日一题Day123】LC1792最大平均通过率 | 堆

最大平均通过率【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(logn)$
    • 空间复杂度：$O(n)$，小顶堆的空间复杂度为$O(n)$