广东省建设执业资格注册中心网站,中国住房和城乡建设部网站造价师注册,微商城网站建设平台,wordpress菜单栏设置最大平均通过率【LC1792】 一所学校里有一些班级#xff0c;每个班级里有一些学生#xff0c;现在每个班都会进行一场期末考试。给你一个二维数组 classes #xff0c;其中 classes[i] [passi, totali] #xff0c;表示你提前知道了第 i 个班级总共有 totali 个学生#…最大平均通过率【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) {PriorityQueuedouble[] pq new PriorityQueuedouble[]((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(nklogn)O(nklogn)O(nklogn)nnn为班级数量kkk为必通过的学生人数向堆中添加元素的时间复杂度为O(logn)O(logn)O(logn)空间复杂度O(n)O(n)O(n)小顶堆的空间复杂度为O(n)O(n)O(n)
