diff options
author | Jack Sangdahl <[email protected]> | 2024-12-14 19:36:16 -0700 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2024-12-14 19:36:16 -0700 |
commit | 879781c5dd20ac3fffec6567a296c6643c7403be (patch) | |
tree | 45406fcbb4948dff4b85bd7e9ec839059d4d224a | |
parent | 6454a6e0421beab63ae3eacb584ef68b9dbac564 (diff) | |
download | leetcode-879781c5dd20ac3fffec6567a296c6643c7403be.tar.gz leetcode-879781c5dd20ac3fffec6567a296c6643c7403be.zip |
1792. maximum average pass ratio
-rw-r--r-- | max_average_pass_ration.cpp | 57 | ||||
-rw-r--r-- | max_average_pass_ration.py | 41 |
2 files changed, 98 insertions, 0 deletions
diff --git a/max_average_pass_ration.cpp b/max_average_pass_ration.cpp new file mode 100644 index 0000000..3da2a9f --- /dev/null +++ b/max_average_pass_ration.cpp @@ -0,0 +1,57 @@ +// 1792. Maximum Average Pass Ratio +#include "leetcode.h" + +/* + * there is a school that has classes of student and each class will be having a + * final exam. you are given a 2d integer array 'classes', where 'classes[i] = + * [pass_i, total_i]'. you know beforehand that in the i'th class, there are + * 'total_i' total students, but only 'pass_i' number of students will pass the + * exam. you are also given an integer 'extraStudents'. there are another + * 'extraStudents' brilliant students that are guaranteed to pass the exam of + * any class they are assigned to. you want to assign each of the + * 'extraStudents' to a class in a way that maximises the average pass ration + * across all classes. return the maximum possible average pass ratio after + * assigning the 'extraStudents'. answers within '10^-5' of the actual answer + * will be accepted. + */ + +struct cmp { + bool operator()(pair<int, int> a, pair<int, int> b) { + double aa = + (a.first + 1) / (double)(a.second + 1) - (a.first) / (double)a.second; + double bb = + (b.first + 1) / (double)(b.second + 1) - (b.first) / (double)b.second; + return aa < bb; + } +}; + +class Solution { +public: + double maxAverageRatio(vector<vector<int>> &classes, int extraStudents) { + double acc = 0; + priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> pq; + for (vector<int> i : classes) + pq.push(make_pair(i[0], i[1])); + while (extraStudents--) { + pair<int, int> curr = pq.top(); + pq.pop(); + curr.first++; + curr.second++; + pq.push(curr); + } + while (!pq.empty()) { + pair<int, int> curr = pq.top(); + pq.pop(); + acc += curr.first / (double)curr.second; + } + return acc / (double)classes.size(); + } +}; + +int main() { + Solution obj; + vvd(int) c1 = {{1, 2}, {3, 5}, {2, 2}}, + c2 = {{2, 4}, {3, 9}, {4, 5}, {2, 10}}; + printf("%f\n", obj.maxAverageRatio(c1, 2)); // expect: 0.78333 + printf("%f\n", obj.maxAverageRatio(c2, 4)); // expect: 0.53485 +} diff --git a/max_average_pass_ration.py b/max_average_pass_ration.py new file mode 100644 index 0000000..b528ea6 --- /dev/null +++ b/max_average_pass_ration.py @@ -0,0 +1,41 @@ +# 1792. Maximum Average Pass Ratio +import heapq + +""" +there is a school that has classes of student and each class will be having a +final exam. you are given a 2d integer array 'classes', where 'classes[i] = +[pass_i, total_i]'. you know beforehand that in the i'th class, there are +'total_i' total students, but only 'pass_i' number of students will pass the +exam. you are also given an integer 'extraStudents'. there are another +'extraStudents' brilliant students that are guaranteed to pass the exam of +any class they are assigned to. you want to assign each of the +'extraStudents' to a class in a way that maximises the average pass ration +across all classes. return the maximum possible average pass ratio after +assigning the 'extraStudents'. answers within '10^-5' of the actual answer +will be accepted. +""" + + +class Solution(object): + def maxAverageRatio(self, classes, extraStudents): + """ + :type classes: List[List[int]] + :type extraStudents: int + :rtype: float + """ + pq = [(a / b - (a + 1) / (b + 1), a, b) for a, b in classes] + heapq.heapify(pq) + while extraStudents: + v, a, b = heapq.heappop(pq) + a, b = a + 1, b + 1 + heapq.heappush(pq, (-(a + 1) / (b + 1) + a / b, a, b)) + extraStudents -= 1 + return sum(a / b for v, a, b in pq) / len(pq) + + +if __name__ == "__main__": + obj = Solution() + print(obj.maxAverageRatio(classes=[[1, 2], [3, 5], [2, 2]], extraStudents=2)) + print( + obj.maxAverageRatio(classes=[[2, 4], [3, 9], [4, 5], [2, 10]], extraStudents=4) + ) |