1792。最大平均通過率

難度：中等

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

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

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

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

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

示例1：

• 輸入： 班級(jí) = [[1,2],[3,5],[2,2]], extraStudents = 2
• 輸出： 0.78333
• 說明：您可以將兩個(gè)額外的學(xué)生分配到第一個(gè)班級(jí)。平均通過率將等于 (3/4 3/5 2/2) / 3 = 0.78333。

示例2：

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

解決方案：

我們可以使用最大堆（優(yōu)先級(jí)隊(duì)列）。這是因?yàn)樵谔砑宇~外的學(xué)生時(shí)，我們需要有效地找到最受益的班級(jí)（最大化通過率的變化）。

方法：

1. 了解增益計(jì)算：

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

2. 使用最大堆:

   • 對(duì)于每個(gè)類，計(jì)算初始增益并將其與類詳細(xì)信息一起插入到最大堆中。
   • 每個(gè)堆元素都是一個(gè)元組：[負(fù)增益，通過，總計(jì)]。 （我們使用負(fù)增益是因?yàn)?PHP 的 SplPriorityQueue 默認(rèn)是 min-heap。）

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

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

4. 計(jì)算最終平均值:

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

讓我們用 PHP 實(shí)現(xiàn)這個(gè)解決方案：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í)隊(duì)列）根據(jù)添加額外學(xué)生時(shí)通過率的潛在改善來確定課程的優(yōu)先級(jí)。
   • 在 PHP 中，SplPriorityQueue 用于堆。優(yōu)先級(jí)值越高，該類越早處理。

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

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

3. 最終平均計(jì)算:

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

4. 精確：

   • 計(jì)算采用浮點(diǎn)運(yùn)算，確保答案精確到要求的 10^-5。

復(fù)雜：

• 時(shí)間復(fù)雜度:

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

• 空間復(fù)雜度:

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

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

聯(lián)系鏈接

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

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

• 領(lǐng)英
• GitHub

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