Leetcode 1792. 最大平均通过率 题解

一所学校里有一些班级，每个班级里有一些学生，现在每个班都会进行一场期末考试。给你一个二维数组classes ，其中 classes[i] = [pass_i, total_i] ，表示你提前知道了第 i 个班级总共有 total_i 个学生，其中只有 pass_i 个学生可以通过考试。

给你一个整数 extraStudents ，表示额外有 extraStudents 个聪明的学生，他们 一定 能通过任何班级的期末考。你需要给这 extraStudents 个学生每人都安排一个班级，使得所有班级的平均通过率最大 。

• 一个班级的通过率等于这个班级通过考试的学生人数除以这个班级的总人数。平均通过率 是所有班级的通过率之和除以班级数目。

请你返回在安排这 extraStudents 个学生去对应班级后的 最大 平均通过率。与标准答案误差范围在 10^-5 以内的结果都会视为正确结果。

本题主要采用贪心的策略来获得最大通过率，以堆的方式进行动态数据的排序

数学基础：如果一个分数 (计算机领域中默认分数为真分数) 的分子分母同时加上一个相同的数，整体将增大

具体思路：

• 本题我们采用堆的方法进行数据存放
• 在堆中排序策略我们采用比较这些班级加上一个聪明小孩后的通过率
• 将classes.size()个班级都假设先加上一个聪明小孩，比较其通过率，采用大根堆排列—降序（顺序不重要）
  • 顺序并不重要，关键是我们借助堆（优先队列）这一工具获得了局部最优解
• 取其中加上聪明小孩后增长率增幅最大的班级，真给他加一个聪明小孩

🔯本题贪心算法的合理性分析：

• 每次都取一个最优解，每次都将最大程度的提高平均通过率
• 数据每次都在动态更新，堆中数据每次都会自动排序
• 由此每次都取到最大的$\Delta 通过率$，由此贪心算法合理！

源码如下：

class Solution {
    struct my_class {  // 定义一个class用于输入到priority_queue中
        int up;
        int dn;
        double ncmp()const {   // 这里就是建立my_class的核心，也是构建堆的核心与必要元素
            return (up+1.0)/(dn+1.0)-(up)/(dn+0.0);
        }
        bool operator < (const my_class& b) const {  // 重载 < 此处为大根堆--降序排列
            return ncmp() < b.ncmp();
        }
        my_class(){}
        my_class(int _up, int _dn):up(_up), dn(_dn){}  // 定义构造函数传入数据
    };
public:
    double maxAverageRatio(vector<vector<int>>& classes, int extraStudents) {
        priority_queue<my_class>q;   // 定义数据类型为my_class的优先队列
        for(int i = 0;i < classes.size(); ++i) { // classes无法直接使用，将其转成my_class
            my_class tmp(classes[i][0], classes[i][1]);
            q.push(tmp);
        }
        while(extraStudents--) {    // 控制聪明小孩的个数，个数为零直接跳出循环
            my_class tmp = q.top();
            q.pop();
            q.push(my_class(tmp.up+1, tmp.dn+1));
            // 此时堆已经为我们根据通过率排好序了，我们只需要取出最优解并且对其执行+1即可
        }
        double ans = 0;
        while(!q.empty()) {
            my_class tmp = q.top();
            q.pop();
            ans += tmp.up*1.0/tmp.dn;  // 循环计算每个班的通过率
        }
        return ans/classes.size();  // 计算整体通过率
    }
};