示范校建设网站维护,it培训机构好,中国十大景观设计公司,做家教什么网站最大平均通过率
难度#xff1a;中等
一所学校里有一些班级#xff0c;每个班级里有一些学生#xff0c;现在每个班都会进行一场期末考试。给你一个二维数组 classes #xff0c;其中 classes[i] [passi, totali] #xff0c;表示你提前知道了第 i 个班级总共有 totali…最大平均通过率
难度中等
一所学校里有一些班级每个班级里有一些学生现在每个班都会进行一场期末考试。给你一个二维数组 classes 其中 classes[i] [passi, totali] 表示你提前知道了第 i 个班级总共有 totali 个学生其中只有 passi 个学生可以通过考试。
给你一个整数 extraStudents 表示额外有 extraStudents 个聪明的学生他们 一定 能通过任何班级的期末考。你需要给这 extraStudents 个学生每人都安排一个班级使得 所有 班级的 平均 通过率 最大 。
一个班级的 通过率 等于这个班级通过考试的学生人数除以这个班级的总人数。平均通过率 是所有班级的通过率之和除以班级数目。
请你返回在安排这 extraStudents 个学生去对应班级后的 最大 平均通过率。与标准答案误差范围在 10−510^{-5}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优先队列
思路
由于班级总数不会变化因此题目所求「最大化平均通过率」等价于「最大化总通过率」。设某个班级的人数为 total\textit{total}total其中通过考试的人数为 pass\textit{pass}pass那么给这个班级安排一个额外通过考试的学生其通过率会增加
pass1total1−passtotal\frac{\textit{pass} 1}{\textit{total} 1} - \frac{\textit{pass}}{\textit{total}}total1pass1−totalpass
我们会优先选择通过率增加量最大的班级这样做的正确性在于给同一个班级不断地增加安排的学生数量时其增加的通过率是单调递减的即
pass2total2−pass1total1pass1total1−passtotal\frac{\textit{pass} 2}{\textit{total} 2} - \frac{\textit{pass} 1}{\textit{total} 1} \frac{\textit{pass} 1}{\textit{total} 1} - \frac{\textit{pass}}{\textit{total}}total2pass2−total1pass1total1pass1−totalpass
因此当以下条件满足时班级 jjj 比班级 iii 优先级更大
passi1totali1−passitotalipassj1totalj1−passjtotalj\frac{\textit{pass}_i 1}{\textit{total}_i 1} - \frac{\textit{pass}_i}{\textit{total}_i} \frac{\textit{pass}_j 1}{\textit{total}_j 1} - \frac{\textit{pass}_j}{\textit{total}_j}totali1passi1−totalipassitotalj1passj1−totaljpassj
化简后可得
(totalj1)×(totalj)×(totali−passi)(totali1)×(totali)×(totalj−passj)(\textit{total}_j 1) \times (\textit{total}_j) \times (\textit{total}_i - \textit{pass}_i) (\textit{total}_i 1) \times (\textit{total}_i) \times (\textit{total}_j - \textit{pass}_j)(totalj1)×(totalj)×(totali−passi)(totali1)×(totali)×(totalj−passj)我们按照上述比较规则将每个班级放入优先队列中进行 extraStudents\textit{extraStudents}extraStudents次操作。每一次操作我们取出优先队列的堆顶元素令其 pass\textit{pass}pass和 total\textit{total}total分别加 111然后再放回优先队列。
最后我们遍历优先队列的每一个班级计算其平均通过率即可得到答案。
复杂度分析
时间复杂度 O((nm)logn)O((n m)\log n)O((nm)logn) 或 O(nmlogn)O(n m\log n)O(nmlogn)其中 nnn 为 classes\textit{classes}classes的长度mmm 等于 extraStudents\textit{extraStudents}extraStudents。每次从优先队列中取出或者放入元素的时间复杂度为 O(logn)O(\log n)O(logn)共需操作 O(nm)O(n m)O(nm) 次故总复杂度为 O((nm)logn)O((n m)\log n)O((nm)logn)。堆化写法的时间复杂度为 O(nmlogn)O(n m\log n)O(nmlogn)。空间复杂度 O(n)O(n)O(n) 或 O(1)O(1)O(1)。使用优先队列需要用到 O(n)O(n)O(n) 的空间但若直接在 classes\textit{classes}classes上原地堆化则可以做到 O(1)O(1)O(1) 额外空间。
import heapq
class Solution:def maxAverageRatio(self, classes: List[List[int]], extraStudents: int) - float:def increasing_rate(a, b):return (a1)/(b1)-a/blis []for i in classes:heapq.heappush(lis, (-increasing_rate(i[0], i[1]), i))for i in range(extraStudents):now heapq.heappop(lis)[1]heapq.heappush(lis, (-increasing_rate(now[0]1, now[1]1), [now[0]1, now[1]1]))return sum([i[1][0]/i[1][1] for i in lis]) / len(lis)来源力扣LeetCode 链接https://leetcode.cn/problems/maximum-average-pass-ratio
