Keshawn_lu's Blog

Leetcode 1792. 最大平均通过率

优先队列
字数统计: 555阅读时长: 2 min
2023/02/19 Share

题目简介：

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

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

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

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

示例 1：

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

示例 2：

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

提示：

  • 1 <= classes.length <= 10^5
  • classes[i].length == 2
  • 1 <= passi <= totali <= 10^5
  • 1 <= extraStudents <= 10^5

思路：

利用优先队列，每次将聪明的学生加入到 平均通过率增量最大的班级中，即(a + 1) / (b + 1) - a / b最大的班级。

最后遍历优先队列，计算最后的平均通过率即可。

代码如下：

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
33
34
35
36
37
38
39
class Solution {
public:
    double maxAverageRatio(vector<vector<int>>& classes, int extraStudents) {

        priority_queue<tuple<double, int, int>> heap;

        for(auto& class_now : classes){

            double x = (double)(class_now[0] + 1) / (class_now[1] + 1) - (double)class_now[0] / class_now[1];

            heap.push({x, class_now[0], class_now[1]});
        }

        for(int i = 0; i < extraStudents; i++){

            auto [_, a, b] = heap.top();
            heap.pop();

            a++;
            b++;

            double now_x = (double)(a + 1) / (b + 1) - (double)a / b;

            heap.push({now_x, a, b});
        }

        double res = 0;
        while(heap.size() > 0){

            auto [_, a, b] = heap.top();
            
            res += (double)a / b;

            heap.pop();
        }

        return res / classes.size();
    }
};
CATALOG
  1. 1. 题目简介：
  2. 2. 思路：
  3. 3. 代码如下：
Total : 424
2023
2022
2021
2020
2019
动态规划 树 深度优先搜索 哈希表 数组 深度优先遍历 单调栈 字符串 双指针 栈 贪心 图 模拟 广度优先搜索 回溯 滑动窗口 二分查找 广度优先遍历 记忆化搜索 数学 链表 前缀和 双向链表 优先队列 拓扑排序 KMP 堆 字典树 递归 并查集 矩阵 位运算 双端队列 吴恩达团队NLP 吴恩达深度学习 线性表
杂谈 算法相关 PAT 2019推理小说阅读计划 NLP 深度学习 大三课程学习 大四课程学习 浙工商OJ 牛客网