1792。最大平均通過(guò)率

難度：中

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

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

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

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

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

範(fàn)例1：

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

範(fàn)例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)注意通過(guò)率的變化。如果不斷增加學(xué)生，通過(guò)率會(huì)發(fā)生什麼變化？班級(jí)中增加的學(xué)生越多，通過(guò)率的變化就越小。
2. 由於通過(guò)率的變化總是隨著您添加的學(xué)生越多而減少，因此您添加到每個(gè)班級(jí)的第一個(gè)學(xué)生就是通過(guò)率變化最大的學(xué)生。
3. 由於每個(gè)班級(jí)的通過(guò)率權(quán)重相等，因此將學(xué)生安排在所有其他班級(jí)中變化最大的班級(jí)始終是最佳選擇。
4. 保留目前類別大小的最大堆，並根據(jù)通過(guò)率的變化對(duì)它們進(jìn)行排序。對(duì)於每個(gè)額外的學(xué)生，取出堆的頂部，更新班級(jí)大小，然後將其放回堆中。

解：

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

方法：

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

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

2. 使用最大堆:

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

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

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

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

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

讓我們用 PHP 實(shí)作這個(gè)解：1792。最大平均通過(guò)率

<?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)先隊(duì)列）根據(jù)添加額外學(xué)生時(shí)通過(guò)率的潛在改善來(lái)確定課程的優(yōu)先順序。
   • 在 PHP 中，SplPriorityQueue 用於堆。優(yōu)先值越高，該類別越早處理。

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

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

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

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

4. 精確：

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

複雜：

• 時(shí)間複雜度:

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

• 空間複雜度:

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

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

聯(lián)絡(luò)連結(jié)

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

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

• 領(lǐng)英
• GitHub

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