Priority Queue

Leetcode 1792. Maximum Average Pass Ratio

Problem

Leetcode 1792. Maximum Average Pass Ratio

Explanation

For each extraStudent add it to a class based on the maximum gain we can achieve.

The gain can be calculated in the following way:

what is the current ratio?
if we add one student to this class, what will be the new ratio?
gain = new ratio - current ratio

We can use a priority queue to dynamically get the maximum gain each time.

Code

Directly use the priority queue

typedef pair<int, int> pii;
class Solution {
public:
    double maxAverageRatio(vector<vector<int>>& classes, int extraStudents) {
        priority_queue<pair<double, pii>> pq;
        for (auto c : classes) {
            double delta = (c[0] + 1) / double(c[1] + 1) - c[0] / double(c[1]); 
            pq.emplace(delta, make_pair(c[0], c[1]));
        }
        while(extraStudents--) {
            auto [a, c] = pq.top();
            pq.pop();
            auto newPass = c.first + 1, newTotal =  c.second + 1;
            double gain = 1.0 * (newPass + 1) / (newTotal + 1) - 1.0 * newPass / newTotal; 
            pq.emplace(gain, make_pair(newPass, newTotal));
        }
        double totalGain = 0;
        while(!pq.empty()) {
            auto [x, y] = pq.top(); pq.pop();
            totalGain += 1.0 * y.first / y.second; 
        }
        return totalGain / classes.size();
    }
};

Use multiple set as a priority queue

This code is from Aoxiang Cui.

This code is really elegant, right?

class Solution {
public:
    struct Node {
        int passed, all;
        bool operator <(const Node& rhs) const {
            double L = 1.0 * (all - passed) / all / (all + 1);
            double R = 1.0 * (rhs.all - rhs.passed) / rhs.all / (rhs.all + 1);
            return L > R;
        }
    };
    double maxAverageRatio(vector<vector<int>>& a, int m) {
        multiset<Node> A;
        for (auto& v : a) {
            A.insert({v[0], v[1]});
        }
        while (m--) {
            auto [x, y] = *A.begin();
            A.erase(A.begin());
            A.insert({x + 1, y + 1});
        }
        double ret = 0;
        for (auto& [x, y] : A) {
            ret += 1.0 * x / y;
        }
        ret /= a.size();
        return ret;
    }
};

Detail about why the struct is defined in that way, a nice related discussion can be found from HERE.

A concise way to use priority queue

class Solution {
public:
    double maxAverageRatio(vector<vector<int>>& classes, int extraStudents) {
        const int n = classes.size();
        auto ratio = [&](int i, int delta = 0) {
            return static_cast<double> (classes[i][0] + delta) / (classes[i][1] + delta);
        };
        priority_queue<pair<double, int>> q;
        for (int i = 0; i < n; ++i) {
            q.emplace(ratio(i, 1) - ratio(i), i);
        }
        while (extraStudents--) {
            const auto [gain, i] = q.top(); q.pop();
            classes[i][0]++;
            classes[i][1]++;
            q.emplace(ratio(i, 1) - ratio(i), i);
        }
        double total_ratio = 0;
        for (int i = 0; i < n; ++i){
            total_ratio += ratio(i);
        }
        return total_ratio / n;
    }
};

The above code is from this video.

If you have question about why using static_cast<double>(x) instead of double(x). See here.