跳转至

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
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def maxAverageRatio(self, classes: List[List[int]], extraStudents: int) -> float:
        def diff(p, t):
            return p / t - (p + 1) / (t + 1)

        Q = []
        for p, t in classes:
            heapq.heappush(Q, (diff(p, t), p, t))

        for _ in range(extraStudents):
            _, p, t = heapq.heappop(Q)
            heapq.heappush(Q, (diff(p + 1, t + 1), p + 1, t + 1))

        ans = 0
        while Q:
            _, p, t = heapq.heappop(Q)
            ans += p / t

        return ans / len(classes)

 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
class Solution {
public:
    double maxAverageRatio(vector<vector<int>>& classes, int extraStudents) {
        auto diff = [] (int p, int t) {
            return 1.0 * (p + 1) / (t + 1) - 1.0 * p / t;
        };

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

        for (auto &c : classes) {
            Q.emplace(diff(c[0], c[1]), c[0], c[1]);
        }

        while (extraStudents--) {
            auto [_, p, t] = Q.top(); Q.pop();

            Q.emplace(diff(p + 1, t + 1), p + 1, t + 1);
        }

        double ans = 0;

        while (!Q.empty()) {
            auto [_, p, t] = Q.top(); Q.pop();

            ans += 1.0 * p / t;
        }

        return ans / (int) classes.size();
    }
};

时间复杂度：\(\mathcal{O}(n\log(m))\)
空间复杂度：\(\mathcal{O}(n)\)

返回顶部

在手机上阅读