1792. 最大平均通过率

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

分析

• 题目：
  • 1792. 最大平均通过率
• 思路：
  • 由于每个班级的通过率随着人数的增加单调递减，所以最大的通过率，必然是前k个人，使用大跟堆，每次取出增益最大的班级进行添加，即可得到最优解。
  • yxc视频讲解

代码

class Solution {
public:double maxAverageRatio(vector<vector<int>>& classes, int extraStudents) {       // 破题点在哪儿呢？最大===>贪心===>堆// 尝试 加到每个班级 选择收益最大的 int n = classes.size();// 经典多路归并问题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();int a = t.a + 1, b = t.b + 1;sum += t.v;heap.push({(a-b)/ (a*(a+1.0)), a, b});}return sum / n;}
};

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

---