// 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); }