ホームページ バックエンド開発 PHPチュートリアル バッグ内のボールの最小制限数

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

Dec 16, 2024 pm 02:33 PM

Minimum Limit of Balls in a Bag

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 サイトの他の関連記事を参照してください。

このウェブサイトの声明
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。

ホットな記事タグ

メモ帳++7.3.1

メモ帳++7.3.1

使いやすく無料のコードエディター

SublimeText3 中国語版

SublimeText3 中国語版

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

ゼンドスタジオ 13.0.1

ゼンドスタジオ 13.0.1

強力な PHP 統合開発環境

ドリームウィーバー CS6

ドリームウィーバー CS6

ビジュアル Web 開発ツール

SublimeText3 Mac版

SublimeText3 Mac版

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

11ベストPHP URLショートナースクリプト(無料およびプレミアム) 11ベストPHP URLショートナースクリプト(無料およびプレミアム) Mar 03, 2025 am 10:49 AM

11ベストPHP URLショートナースクリプト(無料およびプレミアム)

Laravelでフラッシュセッションデータを使用します Laravelでフラッシュセッションデータを使用します Mar 12, 2025 pm 05:08 PM

Laravelでフラッシュセッションデータを使用します

Instagram APIの紹介 Instagram APIの紹介 Mar 02, 2025 am 09:32 AM

Instagram APIの紹介

Laravelテストでの簡略化されたHTTP応答のモッキング Laravelテストでの簡略化されたHTTP応答のモッキング Mar 12, 2025 pm 05:09 PM

Laravelテストでの簡略化されたHTTP応答のモッキング

LaravelのバックエンドでReactアプリを構築する:パート2、React LaravelのバックエンドでReactアプリを構築する:パート2、React Mar 04, 2025 am 09:33 AM

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

PHPのカール:REST APIでPHPカール拡張機能を使用する方法 PHPのカール:REST APIでPHPカール拡張機能を使用する方法 Mar 14, 2025 am 11:42 AM

PHPのカール:REST APIでPHPカール拡張機能を使用する方法

Codecanyonで12の最高のPHPチャットスクリプト Codecanyonで12の最高のPHPチャットスクリプト Mar 13, 2025 pm 12:08 PM

Codecanyonで12の最高のPHPチャットスクリプト

Laravelの通知 Laravelの通知 Mar 04, 2025 am 09:22 AM

Laravelの通知

See all articles