每日一题

Leetcode 每日一题

想要让自己形成好习惯。那就开始写每日一题的blog吧。之前的杂题部分就留着算了。
这里分五个等级来划分我觉得题目的难易程度：夯，顶级，人上人，NPC，拉 来划分（也是玩上了）

20250901

21.1792. 最大平均通过率

1818分的题目，但好像并没有那么难。这里难度给到NPC。

很简单的题目。我们可以发现我们需要做的就是寻找到具有最大增长空间的项，将其增加即可。对于一个班级具有 \((a,b)\), 我们可以有：\(\Delta=\dfrac{b+1}{a+1} - \dfrac{b}{a} = \dfrac{a-b}{a(a+1)}\)。因此这样就需要一个优先级队列就好了。
优先级队列经过 expectedStudents 次插入调整，并最后输出需要 \(O((n+exp)\log{n})\) 的时间复杂度和 \(O(n)\) 空间复杂度。

class Solution {
public:double maxAverageRatio(vector<vector<int>> &classes, int extraStudents) {auto cmp = [&](const vector<int> &a, const vector<int> &b) -> bool {return static_cast<double>(a[1] - a[0])/((long long)a[1] * (a[1] + 1)) <static_cast<double>(b[1] - b[0])/((long long)b[1] * (b[1] + 1));};priority_queue<vector<int>, vector<vector<int>>, decltype(cmp)> pq(cmp);for (const vector<int> & vec : classes) {pq.push(vec);}while(extraStudents > 0) {vector<int> cur = pq.top();pq.pop();cur[0] += 1, cur[1] += 1;extraStudents -= 1;pq.push(cur);}double passRate = 0;int classes_num = classes.size();while(!pq.empty()) {passRate += (static_cast<double>(pq.top()[0]) / pq.top()[1]) / classes_num;pq.pop();}return passRate;}
};