diff options
Diffstat (limited to 'maximum_average_pass_ratio.c')
-rw-r--r-- | maximum_average_pass_ratio.c | 130 |
1 files changed, 130 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); +} |