算法分析:

多路归并:

• 设某个班级的人数为b，其中可以通过考试的人数为a。如果给这个班级安排一个额外的学生，那么该班级的通过率会增加
  (a+1)/(b+1) -a/b

• 而且注意到在不断地给同一个班级安排学生的过程中，增加的通过率是逐渐单调递减的,而且我们考虑时认为只有当一个班级增加一个人后才能增加第二个，这样考虑就有多路归并中指针的作用;

• 所以每次考虑增加一个学生，且在所有班级中选出加入一个学生后通过率增加最大的,这个可以用堆来维护;

C++代码

class Solution {
public:
    double maxAverageRatio(vector<vector<int>>& classes, int extraStudents) {
      struct node{
          double v;//表示当前班级人数为（a,b)时选择它时增加的通过率;
          int a,b;
          bool operator <(const node& p) const{
              return v<p.v;
          }
      };
      priority_queue<node> q;
      double res=0;
      for(auto& c:classes){
           int a=c[0],b=c[1];
           res+=(double) a/b;
           double v=(b-a)/(b*(b+1.0));//初始化
           q.push({v,a,b});
      }
      while(extraStudents--){
           node t=q.top();
           q.pop();
           res+=t.v;
           int a=t.a+1,b=t.b+1;//考虑选择它后(a+1,b+1)的通过率，类似与指针向前移动，将下一个方案放进队列待定
           double v=(b-a)/(b*(b+1.0));
           q.push({v,a,b});
      }
      return res/classes.size();
    }
};