优化网站方法,公司网站域名怎么续费,长春网站建设 找源晟,网站后台免费模板下载文章目录1. 题目2. 解题1. 题目
一所学校里有一些班级#xff0c;每个班级里有一些学生#xff0c;现在每个班都会进行一场期末考试。 给你一个二维数组 classes #xff0c;其中 classes[i] [passi, totali] #xff0c;表示你提前知道了第 i 个班级总共有 totali 个学生…
文章目录1. 题目2. 解题1. 题目
一所学校里有一些班级每个班级里有一些学生现在每个班都会进行一场期末考试。 给你一个二维数组 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 10^5
classes[i].length 2
1 passi totali 10^5
1 extraStudents 10^5来源力扣LeetCode 链接https://leetcode-cn.com/problems/maximum-average-pass-ratio 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
通过率增加的多的优先
// 超时
struct cmp{bool operator()(vectorint a, vectorint b) const{return double(a[0]1)/(a[1]1)-double(a[0])/a[1] double(b[0]1)/(b[1]1)-double(b[0])/b[1];}
};
class Solution {
public:double maxAverageRatio(vectorvectorint classes, int extraStudents) {priority_queuevectorint, vectorvectorint, cmp q;for(auto c : classes)q.push(c);vectorint c;while(extraStudents--){c q.top();q.pop();q.push({c[0]1, c[1]1});}double ans 0;while(!q.empty()){ans q.top()[0]/double(q.top()[1]);q.pop();}return ans/classes.size();}
};参考 zerotrac 的写法才不超时。
tupledouble,int,int auto [d, x, y] q.top()
// 更改写法
class Solution {
public:double maxAverageRatio(vectorvectorint classes, int extraStudents) {priority_queuetupledouble,int,int q;for(auto c : classes)q.push(tuple(delta(c[0], c[1]), c[0], c[1]));while(extraStudents--){auto [d, x, y] q.top();q.pop();q.push(tuple(delta(x1, y1), x1, y1));}double ans 0;while(!q.empty()){auto [d, x, y] q.top();q.pop();ans x/double(y);}return ans/classes.size();}double delta(int x, int y){return double(x1)/(y1)-double(x)/y;}
};1288 ms 91.2 MB C 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
