leet1792. 最大平均通过率

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

---

思路

本题在于分析出分配方法。利用贪心的思想，由于班级个数固定，最大化平均通过率等价于最大化总通过率（各班通过率之和）。这时候就要考虑对每个班来说，分配一个聪明学生，通过率能提升多少（gain）。每次挑选提升最多的班分配一个聪明学生。完了之后，在重新计算下一个通过率提升最多的班，再给分配一个。如此往复，直至所有聪明学生分配完成。

对于一个班级，设总人数为 $t$, 通过人数为 $p$. 则给他分配一个聪明学生，通过率的增益为

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

此外，需要注意到通过率的增加是越来越少的，假如一开始 1/2，

• 2/3 - 1/2 = 1/6
• 3/4 - 2/3 = 1/12
• 4/5 - 3/4 = 1/20
• …

所以最优的分配方式就是，

1. 先挑增益最大的班级分配一个聪明学生
2. 重新计算增益最大的，分配一个
3. 如此往复，直至分配完

那么我们可以维护一个大顶堆，按照 gain 的大小排序，即 gain 最大的在最顶。每次弹出堆顶，分配学生，重新入堆即可完成分配。最后计算平均通过率即可。

Code

class Solution {
public:
    struct Comp {
        bool operator()(const vector<int>& a, const vector<int>& b) {
            int p1 = a[0], t1 = a[1];
            int p2 = b[0], t2 = b[1];
            // (t1-p1)/t1(t1+1) < (t2-p2)/t2(t2+1)
            return 1LL * (t1-p1) * t2 * (t2+1) <
                    1LL* (t2-p2) * t1 * (t1+1);
        };
    };
    double maxAverageRatio(vector<vector<int>>& classes, int extraStudents) {
        priority_queue<vector<int>, vector<vector<int>>, Comp> max_heap(classes.begin(), classes.end());
        while (extraStudents--) {
            vector<int> mx = std::move(max_heap.top());
            max_heap.pop();
            ++mx[0], ++mx[1];
            max_heap.push(mx);
        }
        double ans = 0.0;
        while (!max_heap.empty()) {
            auto& mx = max_heap.top();
            ans += static_cast<double>(mx[0]) / mx[1];
            max_heap.pop();
        }
        return ans / classes.size();
    }
};