leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

1792.cpp (734B)

      1 class Solution {
      2   public:
      3     double maxAverageRatio(const vector<vector<int>> &classes, int extraStudents) const {
      4         typedef tuple<double, int, int> record;
      5         static const auto profit = [](int p, int t) { return (double)(p + 1) / (t + 1) - (double)p / t; };
      6 
      7         double res = 0;
      8         priority_queue<record, vector<record>> pq;
      9         for (const auto &c : classes) {
     10             pq.emplace(profit(c[0], c[1]), c[0], c[1]);
     11             res += (double)c[0] / c[1];
     12         }
     13 
     14         while (extraStudents--) {
     15             const auto [a, p, t] = pq.top();
     16             pq.pop();
     17             pq.emplace(profit(p + 1, t + 1), p + 1, t + 1);
     18             res += a;
     19         }
     20 
     21         return res / size(classes);
     22     }
     23 };