一所学校里有一些班级，每个班级里有一些学生，现在每个班都会进行一场期末考试。给你一个二维数组 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
方法一（超时）
class Solution {
public:double maxAverageRatio(vector<vector<int>>& classes, int extraStudents) {priority_queue<pair<double, int>> q;int n = classes.size();for(int i = 0; i < extraStudents; i++){for(int j = 0; j < n; j++){auto cla = classes[j];double a = (double)cla[0] / cla[1];double b = (double)(cla[0] + 1) / (cla[1] + 1);double k = b - a;q.emplace(k, j);}auto m = q.top();classes[m.second][0]++;classes[m.second][1]++;q = priority_queue<pair<double, int>>();}double ans = 0;for(auto c : classes){double a = (double)c[0] / c[1];ans += a;}return ans / n;}
};
这是我一开始的方法，我们不断寻找最合适的班级来插入聪明的学生，然后我每一轮插入前就先比较classes的增长如何，然后找到会有最大的增长的班级插入聪明的学生。但是这就出现了一个问题，我们计算插入聪明学生的增长，只需要对修改过的classes计算就行，而在该方法中我对每一个classes都进行了运算，其中这部分有大多数计算会是多余的。
方法二
class Solution {
public:double maxAverageRatio(vector<vector<int>>& classes, int extraStudents) {priority_queue<pair<double, int>> q;int n = classes.size();pair<int, int> m;auto gain = [](int pass, int total) -> double {return (double)(pass + 1) / (total + 1) - (double)pass / total;};for(int j = 0; j < n; j++){auto cla = classes[j];q.emplace(gain(cla[0], cla[1]), j);}for(int i = 0; i < extraStudents; i++){auto m = q.top();classes[m.second][0]++;classes[m.second][1]++;q.pop();q.emplace(gain(classes[m.second][0], classes[m.second][1]), classes[m.second][1]);}double ans = 0;for(auto c : classes){double a = (double)c[0] / c[1];ans += a;}return ans / n;}
};
我们在计算增长率的时候只计算修改过的数据，而不会计算所有的数据。
