leetcode 1792. 最大平均通过率 中等

一所学校里有一些班级，每个班级里有一些学生，现在每个班都会进行一场期末考试。给你一个二维数组 classes ，其中 classes[i] = [passi, totali] ，表示你提前知道了第 i 个班级总共有 totali 个学生，其中只有 passi 个学生可以通过考试。

给你一个整数 extraStudents ，表示额外有 extraStudents 个聪明的学生，他们 一定 能通过任何班级的期末考。你需要给这 extraStudents 个学生每人都安排一个班级，使得 所有 班级的 平均 通过率 最大 。

一个班级的 通过率 等于这个班级通过考试的学生人数除以这个班级的总人数。平均通过率 是所有班级的通过率之和除以班级数目。

请你返回在安排这 extraStudents 个学生去对应班级后的 最大 平均通过率。与标准答案误差范围在 10-5 以内的结果都会视为正确结果。

示例 1：

输入：classes = [[1,2],[3,5],[2,2]], extraStudents = 2
输出：0.78333
解释：你可以将额外的两个学生都安排到第一个班级，平均通过率为 (3/4 + 3/5 + 2/2) / 3 = 0.78333 。

示例 2：

输入：classes = [[2,4],[3,9],[4,5],[2,10]], extraStudents = 4
输出：0.53485

提示：

• 1 <= classes.length <= 10^5
• classes[i].length == 2
• 1 <= passi <= totali <= 10^5
• 1 <= extraStudents <= 10^5

分析：给某个班级增加一名必定通过考试的学生，则这个班级的通过率增加为：

每次增加学生一定是向通过率提高最多的班级增加，当满足下面的条件时，班级 j 的优先级比班级 i 更大：

这样依据比较规则，一个一个地将所有学生添加到各个班级里，最后计算平均通过率即可。

typedef struct node
{long long pass,total;
}node;
void up_upgrade(node heap[],int n)
{int t=n;while(t>1){int fat=t/2;if((long long)(heap[t].total+1)*heap[t].total*(heap[fat].total-heap[fat].pass)<(long long)(heap[fat].total+1)*heap[fat].total*(heap[t].total-heap[t].pass)){node temp=heap[t];heap[t]=heap[fat],heap[fat]=temp;t/=2;}else return;}return;
}
void down_upgrade(node heap[],int n)
{int t=1;while(t*2<=n){if(t*2+1<=n){long long cnt1,cnt2,cnt3,cnt4,cnt5,cnt6;cnt1=(heap[t].total+1)*heap[t].total*(heap[t*2].total-heap[t*2].pass);cnt2=(heap[t*2].total+1)*heap[t*2].total*(heap[t].total-heap[t].pass);cnt3=(heap[t].total+1)*heap[t].total*(heap[t*2+1].total-heap[t*2+1].pass);cnt4=(heap[t*2+1].total+1)*heap[t*2+1].total*(heap[t].total-heap[t].pass);cnt5=(heap[t*2].total+1)*heap[t*2].total*(heap[t*2+1].total-heap[t*2+1].pass);cnt6=(heap[t*2+1].total+1)*heap[t*2+1].total*(heap[t*2].total-heap[t*2].pass);if(cnt1<=cnt2&&cnt3<=cnt4)return;else if(cnt2<cnt1&&cnt5<=cnt6){node temp=heap[t];heap[t]=heap[t*2],heap[t*2]=temp;t*=2;}else if(cnt4<cnt3&&cnt6<=cnt5){node temp=heap[t];heap[t]=heap[t*2+1],heap[t*2+1]=temp;t=t*2+1;}}else{long long cnt1,cnt2;cnt1=(heap[t].total+1)*heap[t].total*(heap[t*2].total-heap[t*2].pass);cnt2=(heap[t*2].total+1)*heap[t*2].total*(heap[t].total-heap[t].pass);if(cnt1<=cnt2)return;else {node temp=heap[t];heap[t]=heap[t*2],heap[t*2]=temp;t*=2;}}}return ;
}
double maxAverageRatio(int** classes, int classesSize, int* classesColSize, int extraStudents) {node heap[classesSize+5];double ans=0;for(int i=0;i<classesSize;++i){heap[i+1].pass=classes[i][0],heap[i+1].total=classes[i][1];up_upgrade(heap,i+1);}// for(int i=1;i<=classesSize;++i)//     printf("%d %d %f\n",heap[i].pass,heap[i].total,1.0*heap[i].pass/heap[i].total);// printf("\n");for(int i=0;i<extraStudents;++i){heap[1].pass+=1,heap[1].total+=1;down_upgrade(heap,classesSize);}for(int i=1;i<=classesSize;++i){// printf("%d %d %f\n",heap[i].pass,heap[i].total,1.0*heap[i].pass/heap[i].total);ans+=1.0*heap[i].pass/heap[i].total;}return ans/classesSize;
}