DEV Community
·
1792. 最大平均通过率
💡
原文英文，约1000词，阅读约需4分钟。
📝
内容提要
在一所学校中，给定每个班级的通过人数和总人数，以及额外的优秀学生，目标是合理分配这些学生，以最大化所有班级的平均通过率。通过使用最大堆优先分配对通过率提升最大的班级，最终计算出最大可能的平均通过率。
🎯
关键要点
- 学校中有多个班级，每个班级有通过人数和总人数。
- 目标是合理分配额外的优秀学生，以最大化所有班级的平均通过率。
- 通过率计算公式为通过人数除以总人数，平均通过率为所有班级通过率的总和除以班级数量。
- 使用最大堆优先分配对通过率提升最大的班级。
- 添加学生到班级时，通过率的变化是递减的，首次添加的学生对通过率的影响最大。
- 每个班级的通过率变化需要计算并存入最大堆中。
- 分配完所有额外学生后，计算所有班级的最终平均通过率。
- 时间复杂度为O(extraStudents x log N)，空间复杂度为O(N)。
➡️
