【LeetCode - 每日1题】求最大平均通过率

🌈 个人主页：（时光煮雨）
🔥 高质量专栏：vulnhub靶机渗透测试
👈 希望得到您的订阅和支持~
💡 创作高质量博文(平均质量分95+)，分享更多关于网络安全、Python领域的优质内容！（希望得到您的关注~）

难度 ⭐⭐⭐

前言

一所学校里有一些班级，每个班级里有一些学生，现在每个班都会进行一场期末考试。给你一个二维数组 classes ，其中 classes[i] = [passi, totali] ，表示你提前知道了第 i 个班级总共有 totali 个学生，其中只有 passi 个学生可以通过考试。
给你一个整数 extraStudents ，表示额外有 extraStudents 个聪明的学生，他们 一定 能通过任何班级的期末考。你需要给这 extraStudents 个学生每人都安排一个班级，使得 所有 班级的 平均 通过率 最大 。
一个班级的 通过率 等于这个班级通过考试的学生人数除以这个班级的总人数。平均通过率 是所有班级的通过率之和除以班级数目。
请你返回在安排这 extraStudents 个学生去对应班级后的 最大 平均通过率。与标准答案误差范围在 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
提示：
1 <= classes.length <= 105
classes[i].length == 2
1 <= passi <= totali <= 105
1 <= extraStudents <= 105

要解决这个问题，我们需要最大化所有班级的平均通过率。通过使用最大堆（在Python中使用最小堆模拟）来动态分配额外的学生，每次选择能带来最大通过率提升的班级。以下是代码的详细解释：

✅方法思路

1. ​​问题分析​​：每个班级有通过人数和总人数，额外学生一定通过考试。需要将这些学生分配到班级中，使得所有班级的平均通过率最大。

2. ​​关键观察​​：将额外学生分配到不同班级对通过率的提升不同。提升量可以通过公式计算：(pass_i + 1) / (total_i + 1) - pass_i / total_i。提升量最大的班级应优先分配学生。

3. ​​数据结构选择​​：使用堆（优先队列）来高效选择提升量最大的班级。由于Python的heapq是最小堆，我们存储提升量的负值以实现最大堆的效果。

4. ​​算法步骤​​：

   • 初始化堆，每个元素为提升量的负值、通过人数和总人数。
   • 对于每个额外学生，从堆中取出提升量最大的班级，更新其学生人数，并重新计算提升量后放回堆中。
   • 计算最终所有班级的通过率之和，求平均值。

✅实现代码

from heapq import heappush, heappop, heapify
from typing import List


class Solution:
    def maxAverageRatio(self, classes: List[List[int]], extraStudents: int) -> float:
        # 构建一个最大堆，存储每个班级增加一个学生后通过率的提升值
        # 堆中每个元素为(通过率提升值, 当前通过人数, 当前总人数)
        h = [(a / b - (a + 1) /