526互联

1792. 最大平均通过率

发布时间 2023-04-06 20:17:04作者: zhangk1988

题目描述

给了一个数组，数组值是0<=x<=1的小数
再给了一个值ext，ext可以让以上每个位小数的分子和分母都+1
为怎么分配ext，可以让总和 / 个数最大？

f1-优先队列

基本分析

  1. 可以看出是优先队列，队头需要怎么取？考虑增量，每次将1加在哪个分数中会有最大的增量？
  2. 怎么实现以上思想？因为python默认是最小堆，入队的时候加入-diff(x, y)，用的时候再取 - 出队值
  3. diff函数怎么实现？计算加完以后-加完之前的分数值
  4. 每次处理是什么逻辑？弹出一个增量最大的值，然后将新的可能的增量入q

代码

class Solution:
    def maxAverageRatio(self, classes: List[List[int]], extraStudents: int) -> float:

        n = len(classes)
        diff = lambda x, y : (x + 1) / (y + 1) - x / y
        
        ans = 0.
        q = []
        for x, y in classes:
            ans += x / y
            q.append((-diff(x, y), x, y))
        
        heapq.heapify(q)

        for _ in range(extraStudents):
            d, x, y = heapq.heappop(q)
            ans += -d
            heapq.heappush(q, (-diff(x+1, y+1), x+1, y+1))
        
        return ans / n

总结

  1. 这里没有直接找最小的分数，而是找的最大增量
  2. python小根堆实现大根堆的做法
  3. heapify(q), heappop(q), heappush(q, item)操作