【LeetCode】5703. 最大平均通过率

发表于 更新于 分类于 Valine：
本文字数： 81 阅读时长 ≈ 1 分钟

第232场周赛 5703. 最大平均通过率

思路

  1. 多路归并
  2. 优先队列

$$\frac{b+1}{a+1} - \frac{b}{a} = \frac{a-b}{a(a+1)}$$

代码

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
class Solution {
public:
    double maxAverageRatio(vector<vector<int>>& classes, int extraStudents) {
        struct Node {
            double v;
            int a, b;
            bool operator< (const Node& t) const {
                return v < t.v;
            }
        };
        priority_queue<Node> heap;
        double sum = 0;
        for (auto& c: classes) {
            int a = c[1], b = c[0];
            sum += (double)b / a;
            heap.push({(a - b) / (a * (a + 1.0)), a, b});
        }

        while (extraStudents -- ) {
            auto t = heap.top();
            heap.pop();
            sum += t.v;
            int a = t.a + 1, b = t.b + 1;
            heap.push({(a - b) / (a * (a + 1.0)), a, b});
        }
        return sum / classes.size();
    }
};