5703. 最大平均通过率

算法

贪心、优先队列 $O(n log n)$

• 枚举所有的聪明学生，每次插入到对平均通过率增加贡献最大的那一个班级中，最后对所有班级求一个平均通过率
• 对【平均通过率】增加贡献最大，等价于对【自己班级】增加贡献最大
• 假设某班级的通过比为 $\frac{a}{b}$，增加一个聪明学生之后通过比为 $\frac{a+1}{b+1}$，增加量为 $\frac{a+1}{b+1} - \frac{a}{b} = \frac{b-a}{b(b+1)}$
• 因此，自定义优先队列的排序方式为，按照每个班级的 $\frac{b-a}{b(b+1)}$ 值从大到小排列，每次取出值最大的班级增加一个优秀学生，之后再次放入堆中

C++ 代码

class Solution {
    struct P {
        int a, b;
        double g;
        double calc() const {
            return double(b - a) / b / (b + 1);
        }
        bool operator<(const P& x) const {
            return calc() < x.calc();
        }
    };

   public:
    double maxAverageRatio(vector<vector<int>>& cls, int e) {
        priority_queue<P> pq;
        for (auto& c : cls) {
            P p;
            p.a = c[0], p.b = c[1], p.g = (double)p.a / p.b;
            pq.push(p);
        }
        while (e--) {
            auto q = pq.top();
            pq.pop();
            q.a++, q.b++, q.g = (double)q.a / q.b;
            pq.push(q);
        }
        double ans = 0;
        while (pq.size()) {
            auto q = pq.top();
            pq.pop();
            ans += q.g;
        }
        return ans / cls.size();
    }
};