各店舗に流通する製品の最小化された最大数

2064年。各ストアに流通する製品の最大数を最小限に抑えます

難易度: 中

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

n 個の専門小売店があることを示す整数 n が与えられます。さまざまな量の m 個の製品タイプがあり、これらは 0-indexed 整数配列数量として与えられます。ここで、quantity[i] は i ^番目 の製品タイプの製品の数を表します。

次のルールに従って、すべての製品を小売店に配布する必要があります:

• ストアは最大 1 種類の製品のみを提供できますが、任意の量を提供できます。
• 配布後、各店舗にはある程度の数の商品 (おそらく 0 個) が与えられます。 x を任意の店舗に提供される製品の最大数を表すとします。 x をできるだけ小さくする必要があります。つまり、ストアに提供される製品の最大数を最小化したいとします。

可能な最小の x を返します。

例 1:

• 入力: n = 6、数量 = [11,6]
• 出力: 3
• 説明: 最適な方法の 1 つは次のとおりです。
  • タイプ 0 の 11 個の製品は、次の数量で最初の 4 つの店舗に配布されます: 2、3、3、3
  • タイプ 1 の 6 つの製品は、他の 2 つの店舗に次の数量で分配されます: 3, 3
  • どのストアにも与えられる製品の最大数は max(2, 3, 3, 3, 3, 3) = 3 です。

例 2:

• 入力: n = 7、数量 = [15,10,10]
• 出力: 5
• 説明: 最適な方法の 1 つは次のとおりです。
  • タイプ 0 の 15 個の製品は、最初の 3 つの店舗に次の数量で配布されます: 5、5、5
  • タイプ 1 の 10 個の製品は、次の数量で次の 2 つの店舗に配布されます: 5, 5
  • タイプ 2 の 10 個の製品は、最後の 2 つの店舗に次の数量で配布されます: 5, 5
  • どのストアにも与えられる製品の最大数は max(5, 5, 5, 5, 5, 5, 5) = 5 です。

例 3:

• 入力: n = 1、数量 = [100000]
• 出力: 100000
• 説明: 唯一の最適な方法は次のとおりです。
  • タイプ 0 の 100,000 個の製品は唯一のストアに配布されます。
  • どのストアにも与えられる商品の最大数は max(100000) = 100000 です。

制約:

• m == 量.長さ
• 1 5
• 1 5

ヒント:

1. x がある数値より小さい場合には分配する方法がなく、x がその数値より小さくない場合には常に分配する方法があるという単調な性質が存在します。
2. どの店舗にも与えられる製品の数が k を超えない番号 k が与えられた場合、すべての製品を配布できるかどうかを判断できますか?
3. 関数 canDistribute(k) を実装します。この関数は、どのストアにも k 個を超える製品が提供されないようにすべての製品を配布できる場合は true を返し、それができない場合は false を返します。この関数を使用して、可能な最小の k を二分探索します。

解決策:

任意のストア (x) に割り当てられる製品の最大数について二分検索を使用できます。以下に段階的な説明と PHP ソリューションを示します:

アプローチ

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

   • 下限 (左) を 1 に設定します (各ストアが少なくとも 1 つの製品を入手できるため)。
   • 上限 (右) を数量配列の最大数量として設定します (最悪の場合、1 つのストアが同じタイプのすべての製品を取得します)。
   • 私たちの目標は、x の値を最小化することです (あらゆる店舗に提供される最大の製品)。

2. 二分探索ロジック:

   • 各中間点 x について、どの店舗にも x 個を超える製品が存在しないようにすべての製品を配布することが可能かどうかを確認します。
   • ヘルパー関数 canDistribute(x) を使用して、実現可能性を判断します。

3. 実現可能性チェック (配布可能):

   • 各製品タイプの数量について、店舗ごとに x 製品を超えずにその製品タイプを流通させるために必要な最小店舗数を計算します。
   • すべての製品タイプに必要なストアを合計します。
   • 必要なストアの合計が n 以下の場合、ストアあたりの最大負荷を x として分散が可能です。そうでなければ、それは実現不可能です。

4. 二分探索調整:

   • canDistribute(x) が true を返した場合、x は実行可能な解決策であることを意味しますが、x を最小化したいため、右側の境界を調整します。
   • false が返された場合は、x が小さすぎるため、左の境界を増やします。

5. 結果:

   • 二分探索が完了すると、左に可能な最小の x が保持されます。

このソリューションを PHP で実装してみましょう: 2064。各ストアに配布される製品の最小化された最大数

<?php /**
 * @param Integer $n
 * @param Integer[] $quantities
 * @return Integer
 */
function minimizedMaximum($n, $quantities) {    
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

/**
 * Helper function to check if we can distribute products with maximum `x` per store
 *
 * @param $x
 * @param $quantities
 * @param $n
 * @return bool
 */
function canDistribute($x, $quantities, $n) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
echo minimizedMaximum(6, [11, 6]); // Output: 3
echo minimizedMaximum(7, [15, 10, 10]); // Output: 5
echo minimizedMaximum(1, [100000]); // Output: 100000
?>

説明：

1. canDistribute 関数:

   • 数量ごとに、数量を x で割ることによって必要な最小店舗数が計算されます (各店舗は整数の製品を取得できるため、切り上げには ceil を使用します)。
   • 累積必要ストア数が n を超える場合は false を返します。

2. x の二分探索:

   • 二分探索では、実現可能な最小値に収束するまで x の範囲を繰り返し縮小します。

3. 効率:

   • このソリューションは、二分探索が O(log(max_quantity) * m) で実行され、指定された制約内で実行可能なため、大きな入力サイズ (n と m が最大 10^5) に対して効率的です。

このアプローチでは x が最小限に抑えられ、商品が店舗全体にできるだけ均等に配置されます。

連絡先リンク

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

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

• LinkedIn
• GitHub

以上が各店舗に流通する製品の最小化された最大数の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。