最大平均通過率-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)。