leetcode

commit dde62c66f3c34cd052c4303bd474ec265586f6b7
parent b68b2972a1f5912e4811d7464330e62c12ced158
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Wed,  6 Mar 2024 14:12:46 +0000

1 Random Problem

Diffstat:
A
Problems/1792.cpp
 | 
23
+++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 24 insertions(+), 0 deletions(-)
diff --git a/Problems/1792.cpp b/Problems/1792.cpp
@@ -0,0 +1,23 @@
+class Solution {
+  public:
+    double maxAverageRatio(const vector<vector<int>> &classes, int extraStudents) const {
+        typedef tuple<double, int, int> record;
+        static const auto profit = [](int p, int t) { return (double)(p + 1) / (t + 1) - (double)p / t; };
+
+        double res = 0;
+        priority_queue<record, vector<record>> pq;
+        for (const auto &c : classes) {
+            pq.emplace(profit(c[0], c[1]), c[0], c[1]);
+            res += (double)c[0] / c[1];
+        }
+
+        while (extraStudents--) {
+            const auto [a, p, t] = pq.top();
+            pq.pop();
+            pq.emplace(profit(p + 1, t + 1), p + 1, t + 1);
+            res += a;
+        }
+
+        return res / size(classes);
+    }
+};
diff --git a/README.md b/README.md
@@ -904,6 +904,7 @@ for solving problems.
 |  1786  |   Medium   | [Number of Restricted Paths From First to Last Node](Problems/1786.cpp)                            |
 |  1789  |    Easy    | [Primary Department for Each Employee](Problems/1789.cpp)                                          |
 |  1791  |    Easy    | [Find Center of Star Graph](Problems/1791.cpp)                                                     |
+|  1792  |   Medium   | [Maximum Average Pass Ratio](Problems/1792.cpp)                                                    |
 |  1793  |    Hard    | [Maximum Score of a Good Subarray](Problems/1793.cpp)                                              |
 |  1795  |    Easy    | [Rearrange Products Table](Problems/1795.cpp)                                                      |
 |  1797  |   Medium   | [Design Authentication Manager](Problems/1797.cpp)                                                 |