# 1792. Maximum Average Pass Ratio
###### tags: `Leetcode` `Medium` `Priority Queue` `Greedy`
Link: https://leetcode.com/problems/maximum-average-pass-ratio/
## 思路 $O(NlogN)$ $O(N)$
按照增加一个extraStudents对于class的改变量排序 每次往增加最多的class里增加学生
因为average是所有班级的average的总和/班级数
所以对于整体而言 应该把extraStudent加到使 所有班级的average提高最多的 class里
注意这里的priorityqueue不能直接用lambda表达式也就是

Queue<int[]> pq = new PriorityQueue<>((a,b)->((double)(a[0]+1)/(a[1]+1)-(double)(b[0]+1)/(b[1]+1))

因为如果queue里面item的type和lambda表达式里面的结果不一样会报error
所以需要写成

Queue<int[]> pq = new PriorityQueue<>((a,b)->{
    double diff1 = (double)(a[0]+1)/(a[1]+1) - (double)a[0]/a[1];
    double diff2 = (double)(b[0]+1)/(b[1]+1) - (double)b[0]/b[1];
    if(diff1<diff2) return 1;
    if(diff1<diff2) return 0;
    else return -1;
});

## Code
java

class Solution {
    public double maxAverageRatio(int[][] classes, int extraStudents) {
        Queue<int[]> pq = new PriorityQueue<>((a,b)->{
            double diff1 = (double)(a[0]+1)/(a[1]+1) - (double)a[0]/a[1];
            double diff2 = (double)(b[0]+1)/(b[1]+1) - (double)b[0]/b[1];
            if(diff1<diff2) return 1;
            if(diff1<diff2) return 0;
            else return -1;
        });
        for(int[] singleclass:classes) pq.add(singleclass);
        while(extraStudents!=0){
            int[] lowest = pq.poll();
            lowest[0]++;
            lowest[1]++;
            pq.add(lowest);
            extraStudents--;
        }
        double average = 0;
        while(!pq.isEmpty()){
            average += (double)pq.peek()[0]/pq.peek()[1];
            pq.poll();
        }
        return average/classes.length;
    }
}

c++

typedef array<double,3> AD3;
class Solution {
public:
    double maxAverageRatio(vector<vector<int>>& classes, int extraStudents) {
        priority_queue<AD3> pq;
        for(auto c:classes){
            double p = c[0];
            double t = c[1];
            pq.push({(p+1)/(t+1)-p/t, p, t});
        }
        for(int i=0; i<extraStudents; i++){
            auto [r,p,t] = pq.top();
            pq.pop();
            p += 1;
            t += 1;
            pq.push({(p+1)/(t+1)-p/t, p, t});
        }
        double ans = 0;
        while(!pq.empty()){
            auto [r,p,t] = pq.top();
            pq.pop();
            ans += p/t;
        }
        return ans/classes.size();
    }
};