Description

Submission

class Solution {
public:
    double maxAverageRatio(vector<vector<int>>& classes, int extraStudents) {
        typedef pair<double, int> PDI;
        priority_queue<PDI, vector<PDI>> pq;
        
        int cntOne = 0;
        int n = classes.size();
        for(int i = 0; i < n; ++i) {
            auto& v = classes[i];
            if(v[1] == v[0]) {
                cntOne++;
                continue;
            }
            pq.push({(double)(v[0]+1)/(v[1]+1) - (double)v[0]/v[1], i});
        }
        
        for(; extraStudents > 0 && !pq.empty(); extraStudents--) {
            auto [r, i] = pq.top();  // rate, index
            pq.pop();
            
            auto& v = classes[i];
            v[0] += 1;
            v[1] += 1;
            pq.push({(double)(v[0]+1)/(v[1]+1) - (double)v[0]/v[1], i});
        }
        
        double t = cntOne;
        while(!pq.empty()) {
            auto [r, i] = pq.top();
            pq.pop();
            
            auto& v = classes[i];
            t += (double) v[0] / v[1];
        }
        
        return t / (double)classes.size();
    }
};