@ninijia 在 Leetcode每日一题练习 ------ 1792. 最大平均通过率 中发帖
从Leetcode 每日一题练习继续讨论:
1792. 最大平均通过率
1792. Maximum Average Pass Ratio
题解
本题首先要了解一个分数自身的性质,对一个分数给分子分母同时加1,会使得分数的值向1靠近,意味着若分数小于1,则同时加1会使分数变大,分数大于1,同时加1会使分数变小。
本题学生的通过率都是小于等于1的,因此给通过率小于1的class分配一个通过的学生会使分子分母同时加1使得分数变大。本题要提高总体的平均通过率,需要使分配学生后通过率的增加幅度尽可能大,因此本题可使用最大堆,每次弹出在分子分母同时加1后通过率增加幅度最大的组合,给它分子分母同时加1并计算新的通过率增加幅度重新放入堆中。注意此处为了计算的精确性,需要保留通过率的浮点数和原始的分子分母的整数用于后续计算。
代码
class Solution {
public:
str...