1792.Maximum Average Pass Ratio

tag : Heap, No AC first time

Description

Solution

I feel shamed for I failed to AC it at first time…

Use a heap to store the whole develop rate for each class, and find the max dr and use it.

O(NlogN)

Code

class Solution {
public:
    double maxAverageRatio(vector<vector<int>>& classes, int extraStudents) {
        priority_queue<pair<double, int>, vector<pair<double, int>>, less<>> pq;
        double passrate = 0;
        for(int i = 0; i < classes.size(); i++){
            passrate += 1.0 * classes[i][0] / classes[i][1];
            double pr = calPR(classes[i][0]++,classes[i][1]++);
            pq.emplace(pr, i);
        }
        while(extraStudents--){
            auto [dr, index] = pq.top();
            pq.pop();
            passrate += dr;
            pq.emplace(calPR(classes[index][0]++, classes[index][1]++), index);
        }
        return passrate/classes.size();
    }
    
    double calPR(int p, int t){
        return 1.0 * (p + 1) / (t + 1) - 1.0 * p / t;
    }
};