leetcode_1792 最大平均通过率

本文主要是介绍leetcode_1792 最大平均通过率，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1. 题意

给定一个班级数组，每个班级包括总人数和通过人数。现在可以加入k个通过的学生到任意班级，求

最大的平均通过率。

最大平均通过率

2. 题解

假设某一班级总人数为m, 通过人数为n,则加入一个通过的学生对通过率的增加$diff$为

$$\frac{n+1}{m+1}-\frac{n}{m}=\frac{m-n}{m(m+1)}$$

我们可以通过维护班级的$diff$值的最大堆来解决这个问题。

由于$0\le n\le m\le 1e5$

在比较两个班级的$diff$值的时候可以换为乘法

即判断
$$(m_0-n_0)\ast m_1(m_1+1)<(m_1-n_1)\ast m_0(m_0+1)$$
的布尔值即可

2.1 解法1

class Solution {struct classRate {classRate(int a,int b):pass(a),total(b) {} bool operator <( const classRate &b) const{long long a1 = 1ll * (total - pass) * (b.total) * (b.total + 1);long long a2 = 1ll * (b.total - b.pass) * (total) * (total + 1);return a1 < a2;}int  total;int  pass;};public:double maxAverageRatio(vector<vector<int>>& classes, int extraStudents) {std::priority_queue<classRate> rPq;for(auto &v:classes) {classRate elm(v[0], v[1]);rPq.push(elm);}int i = 0;while (i < extraStudents) {classRate cur = rPq.top();rPq.pop();cur.total += 1;cur.pass += 1;rPq.push(cur);i++;}double res = 0;while (!rPq.empty()) {classRate cur = rPq.top();rPq.pop();res += (double) cur.pass / cur.total;}return res/classes.size();}
};

这篇关于leetcode_1792 最大平均通过率的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---