1792年。最大平均合格率

難易度: 中

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

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

整數(shù)の extraStudents も與えられます。他にも、割り當(dāng)てられたクラスの試験に合格することが保証されている優(yōu)秀な學(xué)生がもう 1 人います。あなたは、クラスすべての平均合格率を最大化する方法で、extraStudents の各生徒をクラスに割り當(dāng)てたいと考えています。

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

extraStudents の學(xué)生を割り當(dāng)てた後の、最大の平均合格率を返します。実際の回答から 10 ^{～ 5} 以內(nèi)の回答が受け入れられます。

例 1:

• 入力: クラス = [[1,2],[3,5],[2,2]]、extraStudents = 2
• 出力: 0.78333
• 説明: 追加の 2 人の生徒を最初のクラスに割り當(dāng)てることができます。平均合格率は (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 _{<= 合計(jì)}i ^{<= 10}5
• ^{1 <= extraStudents <= 10}5

ヒント:

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

解決策:

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

アプローチ：

1. ゲインの計(jì)算を理解する:

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

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

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

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

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

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

   • すべての追加生徒が割り當(dāng)てられたら、すべてのクラスの平均合格率を計(jì)算します。

このソリューションを PHP で実裝してみましょう: 1792。最大平均合格率

  
  
  説明：




ヒープセットアップ:


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



追加生徒の配布:

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



最終平均計(jì)算:


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



精度:


計(jì)算は浮動(dòng)小數(shù)點(diǎn)演算を使用して実行され、必要に応じて答えが 10^-5 まで正確になることが保証されます。





  
  
  複雑：




時(shí)間計(jì)算量:


ヒープの挿入と抽出には O(log N) がかかります。N はクラスの數(shù)です。

extraStudents 反復(fù)の場合、複雑さは O(extraStudents x log N) です。
最終的な合格率の合計(jì)は O(N) です。







空間の複雑さ:


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







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

連絡(luò)先リンク

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

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


LinkedIn
GitHub



          

            
  

            
        

以上が最大平均合格率の詳細(xì)內(nèi)容です。詳細(xì)については、PHP 中國語 Web サイトの他の関連記事を參照してください。