最大平均通过率

标签: 贪心 数组 堆（优先队列）

难度: Medium

一所学校里有一些班级，每个班级里有一些学生，现在每个班都会进行一场期末考试。给你一个二维数组 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

Submission

运行时间: 1059 ms

内存: 51.5 MB

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)

Explain

这道题目使用贪心算法和优先队列（堆）来解决。首先，我们计算每个班级添加一个额外学生后的通过率增加量，即(a / b - (a + 1) / (b + 1))，其中a是通过的学生数，b是班级总人数。我们将这个增加量、通过的学生数和总人数作为一个元组放入一个最小堆中。然后，我们逐个将额外的学生分配给能使通过率增加量最大的班级，即每次从堆中弹出增加量最大的元组，更新该班级的通过人数和总人数，重新计算增加量，然后将更新后的元组再次推入堆中。重复这个过程，直到所有额外的学生都被分配完。最后，我们计算所有班级的平均通过率并返回。

时间复杂度: O(n + k log n)

空间复杂度: O(n)

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)

Explore

优先队列（或堆）在此算法中被使用是因为它能够提供高效的插入和删除最大元素的操作。在每次分配学生时，我们需要寻找当前哪个班级的通过率增加量最大，这是一个典型的最大元素查询操作。使用最大堆可以在O(log n)的时间复杂度内完成这些操作，而如果使用数组或链表，则查找最大元素需要O(n)的时间复杂度。因此，使用堆结构可以显著提高算法的效率。

此定义`a / b - (a + 1) / (b + 1)`准确地反映了在给定班级中添加一个学生后通过率的变化量。这是因为`a / b`是班级当前的通过率，而`(a + 1) / (b + 1)`是在添加一个学生后的新通过率。这个差值表示了通过率的增减，是评估哪个班级通过添加一个学生可以获得最大通过率提升的关键依据。

确实，描述中存在误导。题解中应该使用的是最大堆，因为我们需要优先处理那些使通过率增加量最大的班级。在代码实现中，通常可以通过将增加量取负值的方式使用最小堆来模拟最大堆的行为，从而实现相同的效果。

在这个算法中，每次都是选择可以获得最大正增长的班级来添加学生，所以在分配过程中不会出现通过率减少的情况。每次操作都确保了选择的是增加量最大（即正增长）的班级。算法的目的是最大化整体的平均通过率，而不是单个班级的通过率。因此，虽然单个班级的通过率可能较低，总体平均通过率是在提升的。