LeetCode

Editorial: LeetCode 1792 Maximum Average Pass Ratio

Editorial: LeetCode 1792 Maximum Average Pass Ratio

https://leetcode.com/problems/maximum-average-pass-ratio/ from Amazon

Thinking process:

Ths solution is very strait forward. We always pick the class which will gain most pass ratio if we add one extra student. Keep doing so until we don’t have any extra student.

The way we pick the class is by using a max heap. In C++, we write our own compare function. The compare function will compare the increase in pass ratio if we add one extra student to that class. Knowing this, the rest of the thing is to fiure out how to write this in C++.

Here is the code.

 1class Solution {
 2public:
 3    double diff(int a, int b) {
 4        return (double)(a+1)/(b+1) - (double)a/b;
 5    }
 6    double maxAverageRatio(vector<vector<int>>& classes, int extraStudents) {
 7        auto cmp = [&](const pair<int, int>& a, const pair<int, int>& b) { return diff(a.first, a.second) < diff(b.first, b.second); };
 8        priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)> pq(cmp);
 9        for (auto c : classes) {
10            pq.push({c[0], c[1]});
11        }
12        for (int i=0; i<extraStudents; i++) {
13            auto [p, t] = pq.top(); pq.pop();
14            pq.push({p+1, t+1});
15        }
16        double ans = 0;
17        while (pq.size()) {
18            auto p = pq.top(); pq.pop();
19            ans += (double)p.first/p.second;
20        }
21        return ans/classes.size();
22    }
23};
comments powered by Disqus