1792。最大平均通過率

難度：中等

主題：數(shù)組、貪婪、堆（優(yōu)先隊列）

有一所學(xué)校有學(xué)生班級，每個班級都會有期末考試。給你一個二維整數(shù)數(shù)組類，其中classes[i] = [pass_i,total_i]。你事先知道第i^第班共有_i名學(xué)生，但只有通過_i名學(xué)生才能通過考試。

您還獲得了一個整數(shù) extraStudents。還有另外一些優(yōu)秀的學(xué)生保證通過他們分配到的任何班級的考試。您希望以最大化所有班級的平均通過率的方式將每個extraStudents學(xué)生分配到一個班級。

班級的通過率等于該班級通過考試的學(xué)生人數(shù)除以該班級的學(xué)生總數(shù)。 平均通過率是所有班級的通過率總和除以班級數(shù)量。

分配額外學(xué)生后，返回最大可能的平均通過率。實際答案 10^-5 以內(nèi)的答案將被接受。

示例1：

• 輸入： 班級 = [[1,2],[3,5],[2,2]], extraStudents = 2
• 輸出： 0.78333
• 說明：您可以將兩個額外的學(xué)生分配到第一個班級。平均通過率將等于 (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. 當(dāng)您向班級添加學(xué)生時，請注意通過率的變化。如果不斷增加學(xué)生，通過率會發(fā)生什么變化？班級中添加的學(xué)生越多，通過率的變化就越小。
2. 由于通過率的變化總是隨著您添加的學(xué)生越多而減少，因此您添加到每個班級的第一個學(xué)生就是通過率變化最大的學(xué)生。
3. 由于每個班級的通過率權(quán)重相等，因此將學(xué)生安排在所有其他班級中變化最大的班級始終是最佳選擇。
4. 保留當(dāng)前類大小的最大堆，并根據(jù)通過率的變化對它們進行排序。對于每個額外的學(xué)生，取出堆的頂部，更新班級大小，然后將其放回堆中。

解決方案：

我們可以使用最大堆（優(yōu)先級隊列）。這是因為在添加額外的學(xué)生時，我們需要有效地找到最受益的班級（最大化通過率的變化）。

方法：

1. 了解增益計算：

   • 當(dāng)一個班級添加一名學(xué)生時，通過率的變化可以計算為： 增益 = (通過 1)/(總計 1) - 通過/總計
   • 任務(wù)是通過優(yōu)化分配額外的學(xué)生來最大化所有班級的通過率總和。

2. 使用最大堆:

   • 對于每個類，計算初始增益并將其與類詳細信息一起插入到最大堆中。
   • 每個堆元素都是一個元組：[負增益，通過，總計]。 （我們使用負增益是因為 PHP 的 SplPriorityQueue 默認是 min-heap。）

3. 迭代分配額外的學(xué)生：

   • 彈出堆中增益最大的類。
   • 向該班級添加一名學(xué)生，重新計算增益，并將其推回堆中。
   • 重復(fù)，直到所有額外的學(xué)生都分配完畢。

4. 計算最終平均值:

   • 分配完所有額外學(xué)生后，計算所有班級的平均通過率。

讓我們用 PHP 實現(xiàn)這個解決方案：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
?>

解釋：

1. 堆設(shè)置:

   • 我們使用最大堆（優(yōu)先級隊列）根據(jù)添加額外學(xué)生時通過率的潛在改善來確定課程的優(yōu)先級。
   • 在 PHP 中，SplPriorityQueue 用于堆。優(yōu)先級值越高，該類越早處理。

2. 分配額外的學(xué)生：

   • 對于每個額外的學(xué)生，我們從堆中提取具有最高潛在改進的班級。
   • 在該班級添加一名學(xué)生后，我們重新計算其潛在改進并將其重新插入堆中。

3. 最終平均計算:

   • 分配完所有額外的學(xué)生后，我們計算所有班級的總通過率并返回平均值。

4. 精確：

   • 計算采用浮點運算，確保答案精確到要求的 10^-5。

復(fù)雜：

• 時間復(fù)雜度:

  • 堆插入和提取需要O(log N)，其中N是類的數(shù)量。
  • 對于 extraStudents 次迭代，復(fù)雜度為 O(extraStudents x log N).
  • 最終通過率總和為O(N).

• 空間復(fù)雜度:

  • 堆存儲N個元素，所以空間復(fù)雜度為O(N)。

此實現(xiàn)有效地分配額外的學(xué)生并計算最大平均通過率。

聯(lián)系鏈接

如果您發(fā)現(xiàn)本系列有幫助，請考慮在 GitHub 上給 存儲庫 一個星號或在您最喜歡的社交網(wǎng)絡(luò)上分享該帖子？。您的支持對我來說意義重大！

如果您想要更多類似的有用內(nèi)容，請隨時關(guān)注我：

• 領(lǐng)英
• GitHub

以上是最大平均通過率的詳細內(nèi)容。更多信息請關(guān)注PHP中文網(wǎng)其他相關(guān)文章！