diff options
-rw-r--r-- | maximum_average_pass_ratio.c | 130 | ||||
-rw-r--r-- | maximum_average_pass_ratio.py | 39 |
2 files changed, 169 insertions, 0 deletions
diff --git a/maximum_average_pass_ratio.c b/maximum_average_pass_ratio.c new file mode 100644 index 0000000..5a524bc --- /dev/null +++ b/maximum_average_pass_ratio.c @@ -0,0 +1,130 @@ +// 1792. Maximum Average Pass Ratio +#include "leetcode.h" + +/* + * there is a school that has classes of students 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 there are 'total_i' + * students, but only 'pass_i' students that will pass the exam. you are also + * given in integer 'extraStudents'. there are another 'extraStudents' brilliant + * students that are guaranteed to pass the exam of any class. return the + * maximum possible average pass ratio after assigning the 'extraStudents' + * students. answers within 10^-5 of the actual answer will be accepted. + */ + +struct data { + double gain_rate; + int pass; + int total; +}; + +struct heap { + struct data *pq; + int size; + int capacity; +}; + +struct heap *heap_init(int n) { + struct heap *obj = (struct heap *)malloc(sizeof(struct heap)); + obj->capacity = n; + obj->size = 0; + obj->pq = (struct data *)malloc(n * sizeof(struct data)); + return obj; +} + +void swap(struct data *a, struct data *b) { + struct data tmp = *a; + *a = *b; + *b = tmp; +} + +void heap_up(struct heap *obj, int i) { + while (i > 0) { + int parent = ((i - 1) >> 1); + if (obj->pq[i].gain_rate > obj->pq[parent].gain_rate) { + swap(&(obj->pq[i]), &(obj->pq[parent])); + i = parent; + continue; + } + break; + } +} + +void heap_down(struct heap *obj, int i) { + int largest = i, size = obj->size; + int left = ((i << 1) + 1), right = ((i << 1) + 2); + if (left < size && obj->pq[largest].gain_rate < obj->pq[left].gain_rate) + largest = left; + if (right < size && obj->pq[largest].gain_rate < obj->pq[right].gain_rate) + largest = right; + if (largest != i) { + swap(&(obj->pq[i]), &(obj->pq[largest])); + heap_down(obj, largest); + } +} + +void heap_push(struct heap *obj, struct data new) { + if (obj->size == obj->capacity) { + obj->capacity <<= 1; + obj->pq = + (struct data *)realloc(obj->pq, obj->capacity * sizeof(struct data)); + } + obj->pq[obj->size] = new; + heap_up(obj, obj->size); + ++obj->size; +} + +struct data heap_pop(struct heap *obj) { + struct data top = obj->pq[0]; + obj->pq[0] = obj->pq[--(obj->size)]; + heap_down(obj, 0); + return top; +} + +void heap_free(struct heap *obj) { + free(obj->pq); + free(obj); +} + +static inline double gain(int pass, int total) { + return (double)(pass + 1) / (total + 1) - (double)pass / total; +} + +double maxAverageRatio(int **classes, int classesSize, int *classesColSize, + int extraStudents) { + double ans = 0.0; + struct heap *obj = heap_init(classesSize); + for (int i = 0; i < classesSize; ++i) { + int pass = classes[i][0], total = classes[i][1]; + ans += (double)pass / total; + struct data item = {gain(pass, total), pass, total}; + heap_push(obj, item); + } + for (int i = 0; i < extraStudents; ++i) { + struct data top = heap_pop(obj); + int pass = top.pass, total = top.total; + ans -= (double)pass / total; + ++pass; + ++total; + ans += (double)pass / total; + struct data item = {gain(pass, total), pass, total}; + heap_push(obj, item); + } + heap_free(obj); + return ans; +} + +int main() { + int c1i[3][2] = {{1, 2}, {3, 5}, {2, 2}}, + c2i[4][2] = {{2, 4}, {3, 9}, {4, 5}, {2, 10}}; + struct two_d_arr *c1 = + two_d_arr_init(ARRAY_SIZE(c1i), ARRAY_SIZE(c1i[0]), c1i); + struct two_d_arr *c2 = + two_d_arr_init(ARRAY_SIZE(c2i), ARRAY_SIZE(c2i[0]), c2i); + printf("%f\n", maxAverageRatio(c1->arr, c1->row_size, c1->col_size, + 2)); // expect: 0.78333 + printf("%f\n", maxAverageRatio(c2->arr, c2->row_size, c2->col_size, + 4)); // expect: 0.53485 + two_d_arr_free(c1); + two_d_arr_free(c2); +} diff --git a/maximum_average_pass_ratio.py b/maximum_average_pass_ratio.py new file mode 100644 index 0000000..41aa9fa --- /dev/null +++ b/maximum_average_pass_ratio.py @@ -0,0 +1,39 @@ +# 1792. Maximum Average Pass Ratio +import heapq + +""" +there is a school that has classes of students 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 there are 'total_i' +students, but only 'pass_i' students that will pass the exam. you are also +given in integer 'extraStudents'. there are another 'extraStudents' brilliant +students that are guaranteed to pass the exam of any class. return the +maximum possible average pass ratio after assigning the 'extraStudents' +students. 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 + """ + h = [(a / b - (a + 1) / (b + 1), a, b) for a, b in classes] + heapq.heapify(h) + while extraStudents: + v, a, b = heapq.heappop(h) + a += 1 + b += 1 + heapq.heappush(h, (-(a + 1) / (b + 1) + a / b, a, b)) + extraStudents -= 1 + return sum(a / b for v, a, b in h) / len(h) + + +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) + ) |