题目

一所学校里有一些班级，每个班级里有一些学生，现在每个班都会进行一场期末考试。给你一个二维数组 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 <= 10^5
classes[i].length == 2
1 <= passi <= totali <= 10^5
1 <= extraStudents <= 10^5

解题思路

这是一个非常经典的资源分配问题，其最优解法是使用贪心算法 配合优先队列。

下面是这个问题的完整解题思路。

我们的目标是让所有班级的平均通过率最大化。因为班级总数是固定的，所以这等价于让所有班级的通过率之和最大化。

我们手里有 extraStudents 个学生可以分配。这是一个典型的“把有限的资源分配到不同的地方以获得最大总收益”的问题。贪心算法告诉我们，每一步都做出当前看起来最优的选择。

我们每分配一个学生，都应该把他分配给能让总通过率之和增长最多的那个班级。由于一次只分配一个学生，这个选择只会影响一个班级的通过率。因此，我们应该把这个学生分配给自身通过率提升最大的那个班级。

如何衡量“通过率提升”？

假设一个班级当前有 p 个通过的学生和 t 个总学生，其通过率为 p / t。

如果我们给这个班级增加一个聪明的学生，那么通过的学生会变成 p + 1，总学生会变成 t + 1。新的通过率为 (p + 1) / (t + 1)。

因此，增加一个学生带来的通过率提升值 (Profit) 为：

$$Δ=新通过率−旧通过率= \frac{t+1}{p+1} − \frac{t}{p}$$

我们可以对这个公式进行通分化简：

$$Δ= \frac{t+1}{p+1} − \frac{t}{p} = \frac{t-p}{t(t+1)}$$

这个 Δ 就是我们贪心的依据。在每一步，我们都应该把下一个 extraStudent 分配给能提供最大 Δ 值的那个班级。

算法步骤

直接的模拟（每次都遍历所有班级找到最大的 Δ）效率太低。因为我们每次都想从一堆“收益”中找到最大值，所以需要使用大根堆。

初始化优先队列：
- 创建一个最大堆 (Max Heap)。
- 对于每一个班级 classes[i] = [pass_i, total_i]，计算如果给它增加一个学生，它能带来的通过率提升值 Δ_i。
- 将这个提升值 Δ_i 以及这个班级的信息（比如当前的 pass_i 和 total_i，或者它的索引）作为一个元素存入最大堆。堆会根据 Δ 的大小进行排序，Δ 最大的元素在堆顶。
分配学生（循环 extraStudents 次）：
- 从最大堆的堆顶取出一个元素。这个元素代表了当前能提供最大“收益”的那个班级。
- 假设取出的班级信息是 [p, t]。我们将一个学生分配给它，那么这个班级的新状态就变成了 [p + 1, t + 1]。
- 这个班级未来如果再增加学生，其“收益”会发生变化。我们需要为这个更新后的班级 [p + 1, t + 1] 计算它新的提升值 Δ_new。
- 将这个新的提升值 Δ_new 和更新后的班级信息 [p + 1, t + 1] 重新放回最大堆中。
- 重复这个过程，直到 extraStudents 个学生全部分配完毕。
计算最终结果：
- 当循环结束后，优先队列里存储的就是所有班级经过最优分配后的最终状态（最终的 pass 和 total 人数）。
- 遍历优先队列中剩下的所有元素，计算每个班级的最终通过率 pass / total。
- 将所有班级的最终通过率相加，再除以班级的总数，就得到了我们要求的最大平均通过率。

这个问题的解题思路是贪心，具体实现上采用优先队列来高效地执行贪心策略。每一步都将一个额外的学生分配给能带来最大通过率增量的班级，直到所有学生都分配完毕，从而确保全局的平均通过率达到最大。

具体代码

高时间复杂度

这个方法每次都进行排序找到最大的 Δ

class Solution {
public:
    double maxAverageRatio(vector<vector<int>>& classes, int extraStudents) {

        // 三元组计算∆
        int n = classes.size();
        vector<vector<double>> deltaClsses(n, {0, 0, 0});
        for(int i = 0; i < n; i++)
        {
            deltaClsses[i][0] = classes[i][0];
            deltaClsses[i][1] = classes[i][1];
            deltaClsses[i][2] = ((deltaClsses[i][0] + 1) / (deltaClsses[i][1] + 1)) - (deltaClsses[i][0] / deltaClsses[i][1]);
        }

        // 每次都选择∆最大的结果
        for(int i = 0; i < extraStudents; i++)
        {
            // 排序筛选∆
            sort(deltaClsses.begin(), deltaClsses.end(),
            [](const vector<double>& a, const vector<double>& b)
            {
                return a[2] > b[2];
            });

            deltaClsses[0][0]++;
            deltaClsses[0][1]++;
            deltaClsses[0][2] = ((deltaClsses[0][0] + 1) / (deltaClsses[0][1] + 1)) - (deltaClsses[0][0] / deltaClsses[0][1]);
        }
        
    

        double totalAvgPass = 0;
        for(auto const& singleClasses : deltaClsses)
            totalAvgPass += singleClasses[0] / singleClasses[1];
        return totalAvgPass / n;

    }
};

这段代码里，for 循环内部的这行代码：

// 每次都选择∆最大的结果
for(int i = 0; i < extraStudents; i++)
{
    // 排序筛选∆
    sort(deltaClsses.begin(), deltaClsses.end(), ...); 
    ...
}

你通过在每次循环中对整个数组进行排序来找到 Δ 最大的那个班级。这是一个巨大的性能瓶颈。

sort 的时间复杂度是 O(N log N)，其中 N 是班级的数量。
外层 for 循环要执行 E 次（E 是 extraStudents 的数量）。

因此，算法的这部分时间复杂度高达 O(E * N log N)，这个时间复杂度过高，会导致TTL。

优化的优先队列方法

class Solution {
public:
    // 自定义一个结构体来存储班级信息，代码更清晰
    struct ClassInfo {
        int pass;
        int total;
        double delta; // 增加一个学生带来的通过率提升值

        // 重载小于号运算符，告诉优先队列如何排序
        bool operator<(const ClassInfo& other) const {
            return this->delta < other.delta;
        }
    };

    double maxAverageRatio(vector<vector<int>>& classes, int extraStudents) {
        
        // 创建一个最大堆（优先队列）来存储所有班级的信息
        priority_queue<ClassInfo> pq;

        // 1. 初始化优先队列
        for (const auto& c : classes) {
            int pass = c[0];
            int total = c[1];
            // 计算初始的收益值 delta
            double delta = (double)(total - pass) / ((double)total * (double)(total + 1));
            pq.push({pass, total, delta});
        }

        // 2. 循环分配 extraStudents
        for (int i = 0; i < extraStudents; ++i) {
            // 取出当前收益值最大的班级
            ClassInfo bestClass = pq.top();
            pq.pop();

            // 更新这个班级的人数
            int newPass = bestClass.pass + 1;
            int newTotal = bestClass.total + 1;
            
            // 为更新后的班级计算新的收益值
            double newDelta = (double)(newTotal - newPass) / ((double)newTotal * (double)(newTotal + 1));

            // 将更新后的班级信息重新放回优先队列
            pq.push({newPass, newTotal, newDelta});
        }

        // 3. 计算最终结果
        double totalRatioSum = 0;
        int n = classes.size();

        while (!pq.empty()) {
            ClassInfo finalClass = pq.top();
            pq.pop();
            totalRatioSum += (double)finalClass.pass / finalClass.total;
        }

        return totalRatioSum / n;
    }
};

这个算法的总时间复杂度：

O(N log N) (初始化) + O(E log N) (分配循环) + O(N) (最后计算)

略为$O((N + E) log N)$，这个时间复杂度在$n$和$E$都是$10^5$的量级下是可接受的。

1792. 最大平均通过率

beautifulremi

题目