力扣：1792. 最大平均通过率

 
 
import java.util.PriorityQueue;
 
/**
 * @author xnl
 * @Description:
 * @date: 2022/6/29   22:30
 */
public class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[][] classes = {{1,2},{3,5},{2,2}};
        System.out.println(solution.maxAverageRatio(classes, 2));
    }
 
    /**
     * 使用优先队列加贪心算法
     *  每一次使用收益率最高的作为添加的对象
     *  收益率最高指的就是这里的通过率最低的对象了
     *  需要注意使用double来计算小数值
     *  使用优先队列来进行出栈操作
     * @param classes
     * @param extraStudents
     * @return
     */
    public double maxAverageRatio(int[][] classes, int extraStudents) {
        int n = classes.length;
        PriorityQueue<double[]> queue = new PriorityQueue<double[]>((o1, o2) ->{
            double x = ((o2[0] + 1) / (o2[1] + 1)) - o2[0] / o2[1];
            double y = ((o1[0] + 1) / (o1[1] + 1)) - o1[0] / o1[1];
            if (x > y){
                return 1;
            }
            if (x < y){
                return -1;
            }
            return 0;
        });
 
        // 所有的数放入队列中
        for (int[] aClass : classes) {
            queue.offer(new double[]{aClass[0], aClass[1]});
        }
 
        // 分配学生，每次分配一名
        while (extraStudents != 0){
            double[] poll = queue.poll();
            poll[0] += 1.0;
            poll[1] += 1.0;
            queue.offer(poll);
            extraStudents--;
        }
 
        // 计算最终结果
        double res = 0;
        while (!queue.isEmpty()){
            double[] poll = queue.poll();
            res += poll[0] / poll[1];
        }
        return res / n;
    }
}