跳到主要内容

1792.最大平均通过率

· 阅读需 4 分钟

1、题干​

一所学校里有一些班级，每个班级里有一些学生，现在每个班都会进行一场期末考试。给你一个二维数组 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

2、思路​

这题思路比较容易想到，先用优先队列存储各个班级通过率 classes，优先队列排序逻辑是：假设这个班引入1个逢考必过的学霸 extraStudents 后通过率增长越多排序越靠前。

接着每次安排1个学霸进入通过率增长最多的班级，计算该班级通过率增长值并累加到最初的总通过率 rate，最后求平均就能得到最大平均通过率。

3、代码​

function maxAverageRatio(classes: number[][], c: number): number {
    const pq = new PriorityQueue({
        compare: (a: number[], b: number[]): number => {
            const da = (a[0] + 1) / (a[1] + 1) - a[0] / a[1];
            const db = (b[0] + 1) / (b[1] + 1) - b[0] / b[1];
            return db - da;
        }
    });

    let rate = 0;
    for (let i = 0; i < classes.length; i++) {
        pq.enqueue(classes[i]);
        rate += classes[i][0] / classes[i][1];
    }

    for (; c; c--) {
        const t = pq.dequeue();
        pq.enqueue([t[0] + 1, t[1] + 1]);
        rate += (t[0] + 1) / (t[1] + 1) - t[0] / t[1];
    }

    return rate / classes.length;
};

4、复杂度​

  • 时间复杂度：O(nlogn)O(nlogn)
  • 时间复杂度：O(n)O(n)

5、执行结果​

image.png