最大平均通过率-php教程-PHP中文网

Maximum Average Pass Ratio

1792。最大平均通过率

难度：中等

主题：数组、贪婪、堆（优先队列）

有一所学校有学生班级，每个班级都会有期末考试。给你一个二维整数数组类，其中classes[i] = [pass_i,total_i]。你事先知道第i^第班共有_i名学生，但只有通过_i名学生才能通过考试。

您还获得了一个整数 extraStudents。还有另外一些优秀的学生保证通过他们分配到的任何班级的考试。您希望以最大化所有班级的平均通过率的方式将每个extraStudents学生分配到一个班级。

班级的通过率等于该班级通过考试的学生人数除以该班级的学生总数。 平均通过率是所有班级的通过率总和除以班级数量。

分配额外学生后，返回最大可能的平均通过率。实际答案 10^-5 以内的答案将被接受。

示例1：

输入： 班级 = [[1,2],[3,5],[2,2]], extraStudents = 2
输出： 0.78333
说明：您可以将两个额外的学生分配到第一个班级。平均通过率将等于 (3/4 3/5 2/2) / 3 = 0.78333。

示例2：

输入： 班级 = [[2,4],[3,9],[4,5],[2,10]], extraStudents = 4
输出： 4
解释： 0.53485

约束：

1 5
classes[i].length == 2
1 i i 5
1 5

提示：

当您向班级添加学生时，请注意通过率的变化。如果不断增加学生，通过率会发生什么变化？班级中添加的学生越多，通过率的变化就越小。
由于通过率的变化总是随着您添加的学生越多而减少，因此您添加到每个班级的第一个学生就是通过率变化最大的学生。
由于每个班级的通过率权重相等，因此将学生安排在所有其他班级中变化最大的班级始终是最佳选择。
保留当前类大小的最大堆，并根据通过率的变化对它们进行排序。对于每个额外的学生，取出堆的顶部，更新班级大小，然后将其放回堆中。

解决方案：

我们可以使用最大堆（优先级队列）。这是因为在添加额外的学生时，我们需要有效地找到最受益的班级（最大化通过率的变化）。

方法：

了解增益计算：
- 当一个班级添加一名学生时，通过率的变化可以计算为：增益 = (通过 1)/(总计 1) - 通过/总计
- 任务是通过优化分配额外的学生来最大化所有班级的通过率总和。
使用最大堆:
- 对于每个类，计算初始增益并将其与类详细信息一起插入到最大堆中。
- 每个堆元素都是一个元组：[负增益，通过，总计]。（我们使用负增益是因为 PHP 的 SplPriorityQueue 默认是 min-heap。）
迭代分配额外的学生：
- 弹出堆中增益最大的类。
- 向该班级添加一名学生，重新计算增益，并将其推回堆中。
- 重复，直到所有额外的学生都分配完毕。
计算最终平均值:
- 分配完所有额外学生后，计算所有班级的平均通过率。

让我们用 PHP 实现这个解决方案：1792。最大平均通过率

<?php
/**
 * @param Integer[][] $classes
 * @param Integer $extraStudents
 * @return Float
 */
function maxAverageRatio($classes, $extraStudents) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

/**
 * Calculate the extra pass ratio when a student is added to the class
 *
 * @param $pass
 * @param $total
 * @return float|int
 */
private function extraPassRatio($pass, $total)
{
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage:
$classes = [[1, 2], [3, 5], [2, 2]];
$extraStudents = 2;
echo maxAverageRatio($classes, $extraStudents); // Output: 0.78333

$classes = [[2, 4], [3, 9], [4, 5], [2, 10]];
$extraStudents = 4;
echo maxAverageRatio($classes, $extraStudents); // Output: 0.53485
?>

登录后复制

解释：

堆设置:
- 我们使用最大堆（优先级队列）根据添加额外学生时通过率的潜在改善来确定课程的优先级。
- 在 PHP 中，SplPriorityQueue 用于堆。优先级值越高，该类越早处理。
分配额外的学生：
- 对于每个额外的学生，我们从堆中提取具有最高潜在改进的班级。
- 在该班级添加一名学生后，我们重新计算其潜在改进并将其重新插入堆中。
最终平均计算:
- 分配完所有额外的学生后，我们计算所有班级的总通过率并返回平均值。
精确：
- 计算采用浮点运算，确保答案精确到要求的 10^-5。

复杂：

时间复杂度:
- 堆插入和提取需要O(log N)，其中N是类的数量。
- 对于 extraStudents 次迭代，复杂度为 O(extraStudents x log N).
- 最终通过率总和为O(N).
空间复杂度:
- 堆存储N个元素，所以空间复杂度为O(N)。