[leetcode每日一题]2.19

​​1792. 最大平均通过率​​

难度中等80

一所学校里有一些班级，每个班级里有一些学生，现在每个班都会进行一场期末考试。给你一个二维数组 ​​classes​​ ，其中 ​​classes[i] = [passi, totali]​​ ，表示你提前知道了第 ​​i​​ 个班级总共有 ​​totali​​ 个学生，其中只有 ​​passi​​ 个学生可以通过考试。

给你一个整数 ​​extraStudents​​ ，表示额外有 ​​extraStudents​​ 个聪明的学生，他们 一定 能通过任何班级的期末考。你需要给这 ​​extraStudents​​ 个学生每人都安排一个班级，使得 所有 班级的 平均 通过率 最大 。

一个班级的 通过率 等于这个班级通过考试的学生人数除以这个班级的总人数。平均通过率 是所有班级的通过率之和除以班级数目。

请你返回在安排这 ​​extraStudents​​ 个学生去对应班级后的 最大 平均通过率。与标准答案误差范围在 ​​10-5​​ 以内的结果都会视为正确结果。

示例 1：

extraStudents

示例 2：

extraStudents

提示：

• ​​1 <= classes.length <= 105​​
• ​​classes[i].length == 2​​
• ​​1 <= passi <= totali <= 105​​
• ​​1 <= extraStudents <= 105​​

Solution

首先这道题可以看成是糖水不等式，然后糖的总量是固定的，每次加1个糖进去。由于每个班级是等权重的，所以就要使得每次加糖的增量最大，就能获得最大收益。

每次加使得增量最大，可以看成是一个优先队列的问题，那么用堆就可以了。

那么问题转化为如何求增量。

计算可知增量为,那么以该数的相反数来维护堆即可。

class Solution:
    def maxAverageRatio(self, classes: List[List[int]], extraStudents: int) -> float:
        import heapq
        heap = []
        for class_ in classes:
            heapq.heappush(heap, [-(class_[1] - class_[0])/class_[1]/(class_[1]+1), class_[0], class_[1]])
        for i in range(extraStudents):
            tup = heapq.heappop(heap)
            heapq.heappush(heap, [-(tup[2] - tup[1])/(tup[2] + 1)/(tup[2] + 2), tup[1]+1, tup[2]+1])
        return sum(h[1]/h[2] for h in heap)/len(heap)
            

计算浮点数太慢了，看看官方题解是怎么维护堆的：

最后学习一下heapreplace这个API，可以直接替换堆顶的元素。

附上大佬的优化写法：

class Solution:
    def maxAverageRatio(self, classes: List[List[int]], extraStudents: int) -> float:
        h = [(a / b - (a + 1) / (b + 1), a, b) for a, b in classes]
        heapify(h)
        for _ in range(extraStudents):
            _, a, b = heappop(h)
            a, b = a + 1, b + 1
            heappush(h, (a / b - (a + 1) / (b + 1), a, b))
        return sum(v[1] / v[2] for v in h) / len(classes)

作者：lcbin
链接：https://leetcode.cn/problems/maximum-average-pass-ratio/solution/python3javacgo-yi-ti-yi-jie-you-xian-dui-qrmo/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。