バッグ内のボールの最小制限数

1760。バッグ内のボールの最小制限

難易度: 中

トピック: 配列、二分探索

整数配列 nums が与えられます。ここで、i ^番目 バッグには nums[i] 個のボールが含まれています。整数の maxOperations も指定されます。

次の操作は最大 maxOperations 回実行できます:

• ボールの入った袋を取り出し、正の個のボールが入った 2 つの新しい袋に分けます。
  • たとえば、5 つのボールが入ったバッグは、1 と 4 のボールが入った 2 つの新しいバッグ、または 2 と 3 のボールが入った 2 つの新しいバッグになります。

あなたのペナルティは、バッグ内のボールの最大数です。手術後のペナルティを最小限に抑えたいと考えています。

操作の実行後に可能な最小限のペナルティを返します。

例 1:

• 入力: nums = [9]、maxOperations = 2
• 出力: 3
• 説明:
  • ボール9個が入った袋を6号と3号の2つの袋に分けます。 【9】→> [6,3].
  • ボール6個が入った袋を3号と3号の2つの袋に分けます。 [6,3] -> [3,3,3].
  • 最も多くのボールが入っているバッグには 3 つのボールが入っているため、ペナルティは 3 となり、3 つを返却する必要があります。

例 2:

• 入力: nums = [2,4,8,2]、maxOperations = 4
• 出力: 2
• 説明:
  • ボール8個が入った袋を4号と4号の2つの袋に分けます。 [2,4,8,2] -> [2,4,4,4,2].
  • ボール4個が入った袋を2号と2号の2つの袋に分けます。 [2,4,4,4,2] -> [2,2,2,4,4,2].
  • ボール4個が入った袋をサイズ2と2の2つの袋に分けます。 [2,2,2,4,4,2] -> [2,2,2,2,2,4,2].
  • ボール4個が入った袋をサイズ2と2の2つの袋に分けます。 [2,2,2,2,2,4,2] -> [2,2,2,2,2,2,2,2].
  • 最も多くのボールが入っているバッグには 2 つのボールが入っているため、ペナルティは 2 となり、2 つを返却する必要があります。

制約:

• 1 5
• 1 9

ヒント:

1. バッグの最大サイズがわかったら、質問を変えてみましょう。作成できるバッグの最小数は何個ですか
2. 最大サイズが増加するとバッグの最小数が減少するので、最大サイズを二分探索できることに注意してください

解決策:

二分探索を使用して、可能な最小限のペナルティを見つけることができます。重要な洞察は、特定のペナルティが達成可能かどうかを判断できれば、二分探索を使用して探索範囲を絞り込むことができるということです。

解決する手順:

1. 二分探索セットアップ:

   • 最小ペナルティは 1 です (すべてのボールは 1 つのボールの袋に分割されます)。
   • 最大ペナルティは、nums 配列内の最大の数値です。

2. 実現可能性チェック:

   • 特定のペナルティ Mid について、最大 maxOperations 分割でそれを達成できるかどうかを確認します。
   • これを行うには、各バッグ サイズ (数値) について、すべてのバッグのボールがミッドボール以下になるようにするために必要な分割数を計算します。分割の合計が maxOperations を超える場合、ペナルティ Mid は実行できません。

3. 反復:

   • 二分探索を使用して、ペナルティ Mid が実現可能かどうかに基づいて範囲 [低、高] を調整します。

このソリューションを PHP で実装してみましょう: 1760。バッグ内のボールの最小制限

<?php /**
 * @param Integer[] $nums
 * @param Integer $maxOperations
 * @return Integer
 */
function minimumSize($nums, $maxOperations) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

/**
 * Helper function to check if a penalty is feasible
 *
 * @param $nums
 * @param $maxOperations
 * @param $penalty
 * @return bool
 */
function canAchievePenalty($nums, $maxOperations, $penalty) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example 1
$nums = [9];
$maxOperations = 2;
echo minimumSize($nums, $maxOperations); // Output: 3

// Example 2
$nums = [2, 4, 8, 2];
$maxOperations = 4;
echo minimumSize($nums, $maxOperations); // Output: 2
?>

説明：

1. 二分探索:

   • 検索スペースは 1 から nums 配列の最大数までです。
   • 中間点 Mid は、テストしている現在のペナルティを表します。

2. 実現可能性チェック (canAchievePenalty):

   • 各バッグについて、すべてのバッグのボールがミッドボール以下になるように必要な分割を計算します。
     • ceil(balls / mid) - 1 は必要な分割数を示します。
   • 分割の合計が maxOperations を超える場合、ペナルティは適用できません。

3. 検索スペースを調整:

   • ペナルティが実行可能な場合は、上限を下げます (高 = 中)。
   • そうでない場合は、下限を増やします (低 = 中間 1)。

4. 結果:

   • ループが終了すると、low には実行可能な最小のペナルティが含まれます。

複雑：

• 時間計算量: O(n . log(max(nums)))
  • 二分探索は O(log(max(nums))) で実行され、各中間点の実行可能性チェックには O(n).
• 空間の複雑さ: O(1)。一定の追加スペースのみを使用するためです。

連絡先リンク

このシリーズが役立つと思われた場合は、GitHub で

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

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

• LinkedIn
• GitHub

以上がバッグ内のボールの最小制限数の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。