最大平均合格率

1792年。最大平均合格率

難易度: 中

トピック: 配列、貪欲、ヒープ (優先キュー)

ある学校には生徒のクラスがあり、各クラスで期末試験があります。 2D 整数配列クラスが与えられます。ここで、classes[i] = [pass_i, total_i]。 i^番目のクラスには合計_i人の生徒がいますが、合格_i人の生徒のみが試験に合格することが事前にわかっています。

整数の extraStudents も与えられます。他にも、割り当てられたクラスの試験に合格することが保証されている優秀な学生がもう 1 人います。あなたは、クラスすべての平均合格率を最大化する方法で、extraStudents の各生徒をクラスに割り当てたいと考えています。

クラスの合格率は、試験に合格するクラスの生徒の数をクラスの生徒の総数で割ったものに等しくなります。 平均合格率は、すべてのクラスの合格率の合計をクラス数で割ったものです。

extraStudents の学生を割り当てた後の、最大の平均合格率を返します。実際の回答から 10 ^{～ 5} 以内の回答が受け入れられます。

例 1:

• 入力: クラス = [[1,2],[3,5],[2,2]]、extraStudents = 2
• 出力: 0.78333
• 説明: 追加の 2 人の生徒を最初のクラスに割り当てることができます。平均合格率は (3/4 3/5 2/2) / 3 = 0.78333 となります。

例 2:

• 入力: クラス = [[2,4],[3,9],[4,5],[2,10]]、extraStudents = 4
• 出力: 4
• 説明: 0.53485

制約:

• 1 105
classes[i].length == 2
• ₁ i _{i ⁵}
• ^{1 5}

ヒント:

1. クラスに生徒を追加すると、合格率がどの程度変化するかに注目してください。生徒を追加し続けると、合格率の変化はどうなりますか?クラスに追加する生徒の数が増えるほど、合格率の変化は小さくなります。
2. 追加する生徒が増えるにつれて合格率の変化は常に減少するため、各クラスに最初に追加する生徒が合格率に最も大きな変化をもたらすことになります。
3. 各クラスの合格率は均等に重み付けされるため、他のすべてのクラスの中で最も大きな変化をもたらすクラスに生徒を配置することが常に最適です。
4. 現在のクラス サイズの最大ヒープを保持し、パス率の変化に従って順序付けします。追加の生徒ごとに、ヒープの一番上を取得し、クラスのサイズを更新して、ヒープに戻します。

解決策:

最大ヒープ (優先キュー) を使用できます。これは、生徒を追加するときに最もメリットが得られる (合格率の変化を最大化する) クラスを効率的に見つける必要があるためです。

アプローチ：

1. ゲインの計算を理解する:

   • クラスに生徒を 1 人追加すると、合格率の変化は次のように計算できます。 ゲイン = (パス 1)/(合計 1) - パス/合計
   • 課題は、余分な生徒を最適に配分することで、すべてのクラスの合格率の合計を最大化することです。

2. 最大ヒープを使用する:

   • クラスごとに初期ゲインを計算し、クラスの詳細とともにそれを最大ヒープに挿入します。
   • 各ヒープ要素はタプルです: [負のゲイン、パス、合計]。 (PHP の SplPriorityQueue はデフォルトで min-heap であるため、負のゲインを使用します。)

3. 追加の生徒を反復的に配布する:

   • ヒープから最大のゲインを持つクラスをポップします。
   • そのクラスに生徒を 1 人追加し、ゲインを再計算して、ヒープに戻します。
   • すべての追加生徒が配布されるまで繰り返します。

4. 最終平均の計算:

   • すべての追加生徒が割り当てられたら、すべてのクラスの平均合格率を計算します。

このソリューションを 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
?>

説明：

1. ヒープセットアップ:

   • 私たちは最大ヒープ (優先キュー) を使用して、追加の生徒が追加された場合の合格率の潜在的な向上に基づいてクラスに優先順位を付けます。
   • PHP では、ヒープに SplPriorityQueue が使用されます。優先順位の値が高いほど、クラスは早く処理されます。

2. 追加生徒の配布:

   • 追加の生徒ごとに、ヒープから改善の可能性が最も高いクラスを抽出します。
   • そのクラスに生徒を 1 人追加した後、その潜在的な改善を再計算し、ヒープに再挿入します。

3. 最終平均計算:

   • すべての追加生徒を分配した後、すべてのクラスの合計合格率を計算し、平均を返します。

4. 精度:

   • 計算は浮動小数点演算を使用して実行され、必要に応じて答えが 10^-5 まで正確になることが保証されます。

複雑：

• 時間計算量:

  • ヒープの挿入と抽出には O(log N) がかかります。N はクラスの数です。
  • extraStudents 反復の場合、複雑さは O(extraStudents x log N) です。
  • 最終的な合格率の合計は O(N) です。

• 空間の複雑さ:

  • ヒープには N 要素が格納されるため、空間の複雑さは O(N) になります。

この実装により、追加の生徒が効率的に分散され、最大平均合格率が計算されます。

連絡先リンク

このシリーズが役立つと思われた場合は、GitHub で リポジトリ にスターを付けるか、お気に入りのソーシャル ネットワークで投稿を共有することを検討してください。あなたのサポートは私にとって大きな意味を持ちます!

このような役立つコンテンツがさらに必要な場合は、お気軽にフォローしてください:

• LinkedIn
• GitHub

以上が最大平均合格率の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。