C++ priority queue
The minute the contest is over, I realized the solution was so simple. Wasted the whole time working on a totally wrong path. Sad.\nKey points:\n Calculate rati
The minute the contest is over, I realized the solution was so simple. Wasted the whole time working on a totally wrong path. Sad.\n**Key points:**\n* Calculate ratio gain for inserting a student to each class. Use that ratio gain as key in a priority queue. Bundle class id in the queue with ratio gain.\n* Each time, insert a student into the highest ratio gain class. Recalculate that class\'s ratio gain after and maintain the queue. Repeat until all good students are inserted.\n* Do the ratio average calculation at the end.\n```\n    double maxAverageRatio(vector<vector<int>>& classes, int extraStudents) {\n      std::priority_queue<std::pair<double, int>> q;\n      for (int i=0; i<classes.size(); ++i)\n        q.push({(classes[i][0]+1.0)/(classes[i][1]+1.0) - double(classes[i][0])/double(classes[i][1]), i});\n      for (int i=0; i<extraStudents; ++i) {\n        auto p = q.top();\n        q.pop();\n        ++classes[p.second][0];\n        ++classes[p.second][1];\n        q.push({(classes[p.second][0]+1.0)/(classes[p.second][1]+1.0) - double(classes[p.second][0])/double(classes[p.second][1]), p.second});\n      }\n      double ratios = 0;\n      for (int i=0; i<classes.size(); ++i)\n        ratios += double(classes[i][0])/double(classes[i][1]);\n      return ratios/classes.size();\n    }\n```
['C', 'Heap (Priority Queue)']