1792-最大平均通过率

题目描述

一所学校里有一些班级，每个班级里有一些学生，现在每个班都会进行一场期末考试。给你一个二维数组 classes ，其中 classes[i] = [passi, totali] ，表示你提前知道了第 i 个班级总共有 totali 个学生，其中只有 passi 个学生可以通过考试。

给你一个整数 extraStudents ，表示额外有 extraStudents 个聪明的学生，他们 一定 能通过任何班级的期末考。你需要给这 extraStudents 个学生每人都安排一个班级，使得 所有 班级的 平均 通过率 最大 。

一个班级的 通过率 等于这个班级通过考试的学生人数除以这个班级的总人数。平均通过率 是所有班级的通过率之和除以班级数目。

请你返回在安排这 extraStudents 个学生去对应班级后的 最大 平均通过率。与标准答案误差范围在 10-5 以内的结果都会视为正确结果。

示例 1：

输入：classes = [[1,2],[3,5],[2,2]], extraStudents = 2
输出：0.78333
解释：你可以将额外的两个学生都安排到第一个班级，平均通过率为 (3/4 + 3/5 + 2/2) / 3 = 0.78333 。

示例 2：

输入：classes = [[2,4],[3,9],[4,5],[2,10]], extraStudents = 4
输出：0.53485

提示：

  • 1 <= classes.length <= 105
  • classes[i].length == 2
  • 1 <= passi <= totali <= 105
  • 1 <= extraStudents <= 105

解题思路与题解

我，一个分配天才的荒诞人生

我生来就背负着一个神圣的使命：将聪明的学生分配到各个班级，以最大限度地提高平均通过率。听起来简单？哦，不，这可不是普通的分配工作，这是一场关乎命运的博弈。

起初，我面对的是一片混乱的景象。班级们像一群饥饿的乞丐，伸着碗等待我的施舍。有的班级像[[1,2],[3,5],[2,2]]这样，可怜巴巴地望着我。”看看我们，”第一个班级呻吟着，”只有一半的学生能通过考试，我们是如此卑微。”第二个班级摇摇头，”我们稍好一些，但仍然不够完美。”而第三个班级则骄傲地挺起胸膛，”我们已经完美了，所有学生都能通过！”

我手里有两个额外的天才学生，他们像两颗闪亮的钻石，无论放在哪里都能发光。但问题是，我该把他们放在哪里才能让整个世界（或者说，所有班级的平均通过率）变得更加美好？

我尝试过各种方法。我曾像赌徒一样随意分配，结果可想而知——平庸。我曾像暴君一样强行命令，结果适得其反。我流浪在算法的荒野中，饥肠辘辘，直到有一天，我偷了一只青蛙——是的，一只会计算边际收益的青蛙。

这只青蛙告诉我一个秘密：不要看班级现在的通过率，要看增加一个学生后通过率的提升幅度！这就像是在黑暗中点亮了一盏灯。

我恍然大悟。第一个班级，从1/2到2/3，通过率提升了0.1667；第二个班级，从3/5到4/6，只提升了0.0333；第三个班级，从2/2到3/3，提升为0！显然，第一个班级最需要我的天才学生。

于是，我将第一个天才学生放入第一个班级。然后，我再次计算：第一个班级现在是2/3，再增加一个学生会变成3/4，提升0.0833；第二个班级仍然是提升0.0333；第三个班级还是0。所以，第二个天才学生也应该去第一个班级。

最终，班级们变成了[[3,4],[3,5],[2,2]]，平均通过率达到(3/4 + 3/5 + 2/2) / 3 = 0.78333。

我站在高处，俯瞰着这片被我优化过的土地，突然明白了一个道理：人生就像分配天才学生，不要被表面的光鲜迷惑，而要找到那个能带来最大改变的地方。每一次选择，都应该基于它能带来的边际效益，而不是固有的印象。

这就是我，一个分配天才的顿悟——在资源有限的世界里，最优的分配永远来自于对边际效益的精准计算。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public class LeetCode1792 {

    public static double maxAverageRatio(int[][] classes, int extraStudents) {
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> {
            double x1 = ((a[0] + 1) / (double) (a[1] + 1)) - (a[0] / (double) a[1]);
            double x2 = ((b[0] + 1) / (double) (b[1] + 1)) - (b[0] / (double) b[1]);
            return Double.compare(x2, x1);
        });
        for (int[] c : classes) {
            pq.offer(c);
        }
        while (extraStudents-- > 0) {
            int[] c = pq.poll();
            c[0]++;
            c[1]++;
            pq.offer(c);
        }
        double sum = 0;
        while (!pq.isEmpty()) {
            int[] c = pq.poll();
            sum += (double) c[0] / c[1];
        }
        return sum / classes.length;
    }


    public static void main(String[] args) {
        int[][] classes = {{1, 2}, {3, 5}, {2, 2}};
        int extraStudents = 2;
        System.out.println(maxAverageRatio(classes, extraStudents));
    }
}

image-20250901205134471