バッグ内のボールの最小制限数
Dec 16, 2024 pm 02:33 PM1760。バッグ内のボールの最小制限
難易度: 中
トピック: 配列、二分探索
整数配列 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 です (すべてのボールは 1 つのボールの袋に分割されます)。
- 最大ペナルティは、nums 配列内の最大の数値です。
-
実現可能性チェック:
- 特定のペナルティ Mid について、最大 maxOperations 分割でそれを達成できるかどうかを確認します。
- これを行うには、各バッグ サイズ (数値) について、すべてのバッグのボールがミッドボール以下になるようにするために必要な分割数を計算します。分割の合計が maxOperations を超える場合、ペナルティ Mid は実行できません。
-
反復:
- 二分探索を使用して、ペナルティ 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 から nums 配列の最大数までです。
- 中間点 Mid は、テストしている現在のペナルティを表します。
-
実現可能性チェック (canAchievePenalty):
- 各バッグについて、すべてのバッグのボールがミッドボール以下になるように必要な分割を計算します。
- ceil(balls / mid) - 1 は必要な分割数を示します。
- 分割の合計が maxOperations を超える場合、ペナルティは適用できません。
- 各バッグについて、すべてのバッグのボールがミッドボール以下になるように必要な分割を計算します。
-
検索スペースを調整:
- ペナルティが実行可能な場合は、上限を下げます (高 = 中)。
- そうでない場合は、下限を増やします (低 = 中間 1)。
-
結果:
- ループが終了すると、low には実行可能な最小のペナルティが含まれます。
複雑:
-
時間計算量: O(n . log(max(nums)))
- 二分探索は O(log(max(nums))) で実行され、各中間点の実行可能性チェックには O(n).
- 空間の複雑さ: O(1)。一定の追加スペースのみを使用するためです。
連絡先リンク
このシリーズが役立つと思われた場合は、GitHub でリポジトリ にスターを付けるか、お気に入りのソーシャル ネットワークで投稿を共有することを検討してください。あなたのサポートは私にとって大きな意味を持ちます!
このような役立つコンテンツがさらに必要な場合は、お気軽にフォローしてください:
- GitHub
以上がバッグ内のボールの最小制限数の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。
このウェブサイトの声明
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。

人気の記事
スプリットフィクションを打ち負かすのにどれくらい時間がかかりますか?
3週間前
By DDD
レポ:チームメイトを復活させる方法
3週間前
By 尊渡假赌尊渡假赌尊渡假赌
ハローキティアイランドアドベンチャー:巨大な種を手に入れる方法
3週間前
By 尊渡假赌尊渡假赌尊渡假赌
R.E.P.O.説明されたエネルギー結晶と彼らが何をするか(黄色のクリスタル)
1週間前
By 尊渡假赌尊渡假赌尊渡假赌

人気の記事
スプリットフィクションを打ち負かすのにどれくらい時間がかかりますか?
3週間前
By DDD
レポ:チームメイトを復活させる方法
3週間前
By 尊渡假赌尊渡假赌尊渡假赌
ハローキティアイランドアドベンチャー:巨大な種を手に入れる方法
3週間前
By 尊渡假赌尊渡假赌尊渡假赌
R.E.P.O.説明されたエネルギー結晶と彼らが何をするか(黄色のクリスタル)
1週間前
By 尊渡假赌尊渡假赌尊渡假赌

ホットな記事タグ

メモ帳++7.3.1
使いやすく無料のコードエディター

SublimeText3 中国語版
中国語版、とても使いやすい

ゼンドスタジオ 13.0.1
強力な PHP 統合開発環境

ドリームウィーバー CS6
ビジュアル Web 開発ツール

SublimeText3 Mac版
神レベルのコード編集ソフト(SublimeText3)

ホットトピック
Gmailメールのログイン入り口はどこですか?
7280
9


Java チュートリアル
1622
14


CakePHP チュートリアル
1340
46


Laravel チュートリアル
1257
25


PHP チュートリアル
1205
29



LaravelのバックエンドでReactアプリを構築する:パート2、React
