Maximum Average Pass Ratio LeetCode solution in C++

1
struct cmp {
2
  bool operator()(pair<int, int> a, pair<int, int> b) {
3
    double ad = (a.first + 1) / (double)(a.second + 1) - (a.first) / (double)a.second;
4
    double bd = (b.first + 1) / (double)(b.second + 1) - (b.first) / (double)b.second;
5
    return ad < bd;
6
  }
7
};
8

9
class Solution {
10
 public:
11
  double maxAverageRatio(vector<vector<int>> &classes, int extraStudents) {
12
    double acc = 0;
13
    priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> que;
14
    for (vector<int> i : classes) que.push(make_pair(i[0], i[1]));
15
    while (extraStudents--) {
16
      pair<int, int> cur = que.top();
17
      que.pop();
18
      cur.first++, cur.second++;
19
      que.push(cur);
20
    }
21
    while (!que.empty()) {
22
      pair<int, int> cur = que.top();
23
      que.pop();
24
      acc += cur.first / (double)cur.second;
25
    }
26
    return acc / (double)classes.size();
27
  }
28
};