1792. 最大平均通过率（Rating 1817）

以下内容偏向于记录个人练习过程及思考，非常规题解内容

题目

1792. 最大平均通过率

Rating 1817

思路

对于某一个班级，设其通过人数和总人数分别为x, y，对应通过率则为：x / y

对于这个班级，增加一个人所能增加对通过率则为：s = (x + 1) / (y + 1) - x / y

为了最终平均通过率的增加，应当尽量找s尽可能大的班级去增加通过人数

这个过程可以通过维护优先队列完成

代码

def score(x: int, y: int) -> float:
        return x / y - (x + 1) / (y + 1) # 因为python中默认是小顶堆，所以取反了

class Solution:
    def maxAverageRatio(self, classes: List[List[int]], extraStudents: int) -> float:
        hp = [(score(x, y), idx) for idx, (x, y) in enumerate(classes)]
        heapq.heapify(hp) # 以s为key建立小顶堆
        for i in range(extraStudents): # 将堆顶的班级，依次增加通过人数
            _, idx = heapq.heappop(hp)
            classes[idx][0] += 1
            classes[idx][1] += 1
            x, y = classes[idx]
            heapq.heappush(hp, (score(x, y), idx))
        ret = 0.
        for x, y in classes:
            ret += x / y
        return ret / len(classes)