1792_最大平均通过率

类型：堆

• 1792. 最大平均通过率 💛

  https://leetcode-cn.com/problems/maximum-average-pass-ratio/

  ❓ 有一个表示班级情况的数组 classes，classes[i] = [pass, total] 表示 i 号班级总共有 total 名学生，其中只有 pass 名能够通过期末考试。现在额外有 extraStudents 名好学生（一定能通过考试），请将这些学生安排到班级中，使所有班级的通过率之和最大。 💡 堆

  对于一个班级 [pass, total] 来说，插入一名好学生后，通过率的提升程度为 (pass+1)/(total+1) - pass/total，我们要使好学生插入后，所有班级的通过率之和最大，自然就要把好学生往提升最显著的班级插。

  class Solution:
      def maxAverageRatio(self, classes: List[List[int]], extraStudents: int) -> float:
          improvingClasses = [(pa / total - (pa + 1)/(total + 1), pa, total) for [pa, total] in classes]
          heapq.heapify(improvingClasses)
  
          while extraStudents:
              (_, pa, total) = heapq.heappop(improvingClasses)
              pa += 1
              total += 1
              heapq.heappush(improvingClasses, (pa / total - (pa + 1)/(total + 1), pa, total))
              extraStudents -= 1
  
          percentSum = sum(pa / total for (_, pa, total) in improvingClasses)
          return float(format(percentSum / len(classes), '.5f'))