1792-最大平均通过率

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 17:01:07 2023-09-13 17:01:07 Updated    

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

方法一：优先队列

思路与算法

由于班级总数不会变化，因此题目所求「最大化平均通过率」等价于「最大化总通过率」。设某个班级的人数为 total，其中通过考试的人数为 pass，那么给这个班级安排一个额外通过考试的学生，其通过率会增加：

\textit{pass} + 1}{\textit{total} + 1} - \textit{pass} }{\textit{total}

我们会优先选择通过率增加量最大的班级，这样做的正确性在于给同一个班级不断地增加安排的学生数量时，其增加的通过率是单调递减的，即：

\textit{pass} + 2}{\textit{total} + 2} - \textit{pass} + 1}{\textit{total} + 1} < \textit{pass} + 1}{\textit{total} + 1} - \textit{pass} }{\textit{total}

因此当以下条件满足时，班级 j 比班级 i 优先级更大：

\textit{pass}_i + 1}{\textit{total}_i + 1} - \textit{pass}_i}{\textit{total}_i} < \textit{pass}_j + 1}{\textit{total}_j + 1} - \textit{pass}_j}{\textit{total}_j

化简后可得：

(\textit{total}_j + 1) \times (\textit{total}_j) \times (\textit{total}_i - \textit{pass}_i) < (\textit{total}_i + 1) \times (\textit{total}_i) \times (\textit{total}_j - \textit{pass}_j)

我们按照上述比较规则将每个班级放入优先队列中，进行 extraStudents 次操作。每一次操作，我们取出优先队列的堆顶元素，令其 pass 和 total 分别加 1，然后再放回优先队列。

最后我们遍历优先队列的每一个班级，计算其平均通过率即可得到答案。

代码

[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Entry:
    __slots__ = 'p', 't'

    def __init__(self, p: int, t: int):
        self.p = p
        self.t = t

    def __lt__(self, b: 'Entry') -> bool:
        return (self.t - self.p) * b.t * (b.t + 1) > (b.t - b.p) * self.t * (self.t + 1)

class Solution:
    def maxAverageRatio(self, classes: List[List[int]], extraStudents: int) -> float:
        h = [Entry(*c) for c in classes]
        heapify(h)
        for _ in range(extraStudents):
            heapreplace(h, Entry(h[0].p + 1, h[0].t + 1))
        return sum(e.p / e.t for e in h) / len(h)
[sol1-C++]
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:
    struct Ratio {
        int pass, total;
        bool operator < (const Ratio& oth) const {
            return (long long) (oth.total + 1) * oth.total * (total - pass) < (long long) (total + 1) * total * (oth.total - oth.pass);
        }
    };

    double maxAverageRatio(vector<vector<int>>& classes, int extraStudents) {
        priority_queue<Ratio> q;
        for (auto &c : classes) {
            q.push({c[0], c[1]});
        }

        for (int i = 0; i < extraStudents; i++) {
            auto [pass, total] = q.top();
            q.pop();
            q.push({pass + 1, total + 1});
        }

        double res = 0;
        for (int i = 0; i < classes.size(); i++) {
            auto [pass, total] = q.top();
            q.pop();
            res += 1.0 * pass / total;
        }
        return res / classes.size();
    }
};
[sol1-Java]
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
class Solution {
    public double maxAverageRatio(int[][] classes, int extraStudents) {
        PriorityQueue<int[]> pq = new PriorityQueue<int[]>((a, b) -> {
            long val1 = (long) (b[1] + 1) * b[1] * (a[1] - a[0]);
            long val2 = (long) (a[1] + 1) * a[1] * (b[1] - b[0]);
            if (val1 == val2) {
                return 0;
            }
            return val1 < val2 ? 1 : -1;
        });
        for (int[] c : classes) {
            pq.offer(new int[]{c[0], c[1]});
        }

        for (int i = 0; i < extraStudents; i++) {
            int[] arr = pq.poll();
            int pass = arr[0], total = arr[1];
            pq.offer(new int[]{pass + 1, total + 1});
        }

        double res = 0;
        for (int i = 0; i < classes.length; i++) {
            int[] arr = pq.poll();
            int pass = arr[0], total = arr[1];
            res += 1.0 * pass / total;
        }
        return res / classes.length;
    }
}
[sol1-Golang]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
func maxAverageRatio(classes [][]int, extraStudents int) (ans float64) {
    h := hp(classes)
    heap.Init(&h)
    for ; extraStudents > 0; extraStudents-- {
        h[0][0]++
        h[0][1]++
        heap.Fix(&h, 0)
    }
    for _, c := range h {
        ans += float64(c[0]) / float64(c[1])
    }
    return ans / float64(len(classes))
}

type hp [][]int
func (h hp) Len() int { return len(h) }
func (h hp) Less(i, j int) bool { a, b := h[i], h[j]; return (a[1]-a[0])*b[1]*(b[1]+1) > (b[1]-b[0])*a[1]*(a[1]+1) }
func (h hp) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (hp) Push(interface{})     {}
func (hp) Pop() (_ interface{}) { return }

复杂度分析

  • 时间复杂度：O((n + m)\log n) 或 O(n + m\log n)，其中 n 为 classes 的长度，m 等于 extraStudents。每次从优先队列中取出或者放入元素的时间复杂度为 O(\log n)，共需操作 O(n + m) 次，故总复杂度为 O((n + m)\log n)。堆化写法的时间复杂度为 O(n + m\log n)。

  • 空间复杂度：O(n) 或 O(1)。使用优先队列需要用到 O(n) 的空间，但若直接在 classes 上原地堆化，则可以做到 O(1) 额外空间。

 Comments
On this page
1792-最大平均通过率