最も裕福な山からギフトを受け取る

2558。最も裕福な山からギフトを受け取りましょう

難易度: 簡単

トピック: 配列、ヒープ (優先キュー)、シミュレーション

さまざまな山のギフトの数を示す整数配列ギフトが与えられます。毎秒、次のことを行います:

• ギフトの最大数の山を選択してください。
• ギフトの最大数の山が複数ある場合は、いずれかを選択します。
• 山の中のギフトの数の平方根の床を残します。残りのギフトを受け取ってください。

k 秒後に残っているギフトの数を返します。

例 1:

• 入力: ギフト = [25,64,9,4,100]、k = 4
• 出力: 29
• 説明: ギフトは次の方法で受け取られます:
  • 最初の 1 秒で最後の山が選択され、10 個のギフトが残ります。
  • 次に 2 番目の山が選択され、8 つのギフトが残ります。
  • その後、最初の山が選択され、5 つのギフトが残ります。
  • 最後に、最後の山が再度選択され、3 つのギフトが残ります。
  • 最後に残ったギフトは [5,8,9,4,3] なので、残っているギフトの総数は 29 個です。

例 2:

• 入力: ギフト = [1,1,1,1]、k = 4
• 出力: 4
• 説明: この場合、どの山を選んだかに関係なく、各山にギフトを 1 つ残さなければなりません。
  • つまり、山を持ち帰ることはできません。
  • つまり、残りのギフトは合計 4 つです。

制約:

• 1 3
• 1 9
• 1 3

ヒント:

1. 配列内の最大のギフトをどのように追跡できますか
2. 数値の平方根を見つける効率的な方法は何ですか?
3. ギフトが特定の順序であることを確認しながら、ギフトの値を合計し続けることができますか?
4. ここで優先キューまたはヒープを使用できますか?

解決策:

最大数のギフトを含む山を繰り返し選択する必要があるため、最大ヒープ (優先キュー) を利用できます。最大ヒープを使用すると、一定時間内に最大の山に効率的にアクセスし、山からギフトを取得した後にヒープを更新できます。

アプローチ：

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

   • 最大数のギフトの山を繰り返し取得する必要があるため、最大ヒープ (優先キュー) が理想的です。 PHP では、SplPriorityQueue を使用できます。これは、デフォルトで最大ヒープとして機能する優先キューです。
   • SplPriorityQueue はデフォルトで最小ヒープであるため、最大ヒープをシミュレートするには、ギフトの数を負の値として挿入します。負の値を挿入すると、最小の負の値が元の最大の数値を表します。

2. 毎秒の処理:

   • 毎秒ごとに、ヒープから最大数のギフトの山をポップします。
   • その山のギフトの数の平方根を除くすべてのギフトを受け取ります。
   • 変更されたパイルをヒープにプッシュします。

3. 終了:

   • k 秒後、またはすべての秒を処理したら停止します。

このソリューションを PHP で実装してみましょう: 2558。最も裕福な山からギフトを受け取りましょう

<?php /**
 * @param Integer[] $gifts
 * @param Integer $k
 * @return Integer
 */
function pickGifts($gifts, $k) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage:
$gifts1 = [25, 64, 9, 4, 100];
$k1 = 4;
echo pickGifts($gifts1, $k1) . "\n"; // Output: 29

$gifts2 = [1, 1, 1, 1];
$k2 = 4;
echo pickGifts($gifts2, $k2) . "\n"; // Output: 4
?>

説明：

1. ヒープの初期化:

   • SplPriorityQueue は、最大ヒープをシミュレートするために使用されます。 insert メソッドを使用すると、優先順位を付けて要素をヒープにプッシュできます。

2. 最大のパイルを処理しています:

   • k 回の反復で、extract を使用して最大の山が抽出されます。
   • 残されたギフトの数は、floor(sqrt(...)) を使用して、現在の最大の山の平方根の床として計算されます。
   • 削減されたパイルはヒープに再挿入されます。

3. 残りのギフトを合計しています:

   • k 回の操作の後、ヒープ内のすべての要素が抽出され、合計されて、残りのギフトの総数が取得されます。

4. エッジケース:

   • ギフトが空の場合、結果は 0 になります。
   • k が可能な演算数より大きい場合、アルゴリズムはそれを適切に処理します。

時間計算量:

• ヒープ操作 (挿入と抽出): 各ヒープ操作 (挿入と抽出) には O(log n) がかかります。nは山の数です。
• k 個の操作によるループ: k 操作を実行します。それぞれの操作にはヒープの抽出と挿入が含まれ、両方とも O(log n).

したがって、合計時間計算量は

O(k log n) です。ここで、n はパイルの数、k は秒数です。

チュートリアルの例:

入力用:

<?php /**
 * @param Integer[] $gifts
 * @param Integer $k
 * @return Integer
 */
function pickGifts($gifts, $k) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage:
$gifts1 = [25, 64, 9, 4, 100];
$k1 = 4;
echo pickGifts($gifts1, $k1) . "\n"; // Output: 29

$gifts2 = [1, 1, 1, 1];
$k2 = 4;
echo pickGifts($gifts2, $k2) . "\n"; // Output: 4
?>

1. 最初、優先キューには [25, 64, 9, 4, 100] の山があります。
2. 1 秒後: 100 個を選択し、10 個を残します。残りのギフトは [25、64、9、4、10] です。
3. 2 秒後: 64 を選択し、8 を残します。残りのギフトは [25、8、9、4、10] です。
4. 3 秒後: 25 を選択し、5 を残します。残りのギフトは [5、8、9、4、10] です。
5. 4 秒後: 10 個を選択し、3 個を残します。残りのギフトは [5、8、9、4、3] です。

残りのギフトの合計は 5 8 9 4 3 = 29 です。

このアプローチは、最大ヒープを使用して問題を効率的に解決し、指定された制約内で適切にパフォーマンスを発揮します。

連絡先リンク

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

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

• LinkedIn
• GitHub

以上が最も裕福な山からギフトを受け取るの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。