maximum-average-pass-ratio.cpp

// Time:  O(n + mlogn)
// Space: O(n)

class Solution {
public:
    double maxAverageRatio(vector<vector<int>>& classes, int extraStudents) {
        static const auto& profit = [](double a, double b) {
            return (a + 1) / (b + 1) - a / b;
        };

        vector<tuple<double, int, int>> max_heap;
        for (const auto& c : classes) {
            max_heap.emplace_back(profit(c[0], c[1]), c[0], c[1]);
        }
        make_heap(begin(max_heap), end(max_heap));
        for (; extraStudents > 0; --extraStudents) {
            auto [_, a, b] = max_heap.front();
            ++a, ++b;
            pop_heap(begin(max_heap), end(max_heap)); max_heap.pop_back();
            max_heap.emplace_back(profit(a, b), a, b); push_heap(begin(max_heap), end(max_heap));
        }
        return accumulate(cbegin(max_heap), cend(max_heap), 0.0,
                          [](const auto& total, const auto& x) {
                              return total + float(get<1>(x)) / get<2>(x);
                          }) / size(classes);
    }
};