最小化分配到任何商店的產品數量

2064。最小化分配到任何商店的產品數量

難度：中

主題：陣列、二分查找

給你一個整數n，表示有n家專賣零售店。有 m 個不同數量的產品類型，以 0 索引 整數數組數量形式給出，其中數量[i] 表示第 i^th 個產品類型的產品數量。

您需要依照以下規則將所有產品分送到零售店：

• 一家商店只能提供至多一種產品類型，但可以提供任意數量。
• 分發後，每個商店都會獲得一定數量的產品（可能是0）。令 x 代表向任何商店提供的最大產品數量。您希望 x 盡可能小，即您希望最小化向任何商店提供的最大產品數量。

回傳最小可能的x。

範例1：

• 輸入： n = 6，數量 = [11,6]
• 輸出： 3
• 解釋： 一個最佳方法是：
  • 類型 0 的 11 種產品分配給前四家商店，數量如下：2, 3, 3, 3
  • 類型 1 的 6 種產品按以下數量分發給其他兩家商店：3, 3
  • 給予任何商店的最大產品數量為 max(2, 3, 3, 3, 3, 3) = 3.

範例2：

• 輸入： n = 7，數量 = [15,10,10]
• 輸出： 5
• 解釋： 一個最佳方法是：
  • 類型 0 的 15 種產品分配給前三家商店，數量如下：5, 5, 5
  • 10 種類型的產品以以下數量分發到接下來的兩家商店：5, 5
  • 類型 2 的 10 種產品以以下數量分發到最後兩家商店：5, 5
  • 給予任何商店的最大產品數量為 max(5, 5, 5, 5, 5, 5, 5) = 5。

範例 3：

• 輸入： n = 1，數量 = [100000]
• 輸出： 100000
• 解釋：唯一的最佳方法是：
  • 100000個0型產品分送到唯一的商店。
  • 給予任何商店的最大產品數量為 max(100000) = 100000。

約束：

• m == 數量.長度
• 1 5
• 1 5

提示：

1. 存在單調性，當x小於某個數時，就沒有辦法分配，而當x不小於該數時，總會有辦法分配。
2. 如果給你一個數字k，其中任何商店提供的產品數量不超過k，你能確定是否所有產品都可以分發嗎？
3. 實作一個函數 canDistribute(k)，如果您可以分發所有產品，則傳回 true，這樣任何商店都不會獲得超過 k 個產品，如果不能，則傳回 false。使用此函數二分查找盡可能小的 k。

解：

我們可以對分配給任何商店的最大可能產品數量 (x) 使用二分搜尋。以下是逐步說明和 PHP 解決方案：

方法

1. 二分搜尋設定:

   • 將下限（左）設為 1（因為每家店至少可獲得 1 個產品）。
   • 將上限（右）設定為數量數組中的最大數量（在最壞的情況下，一個商店獲得一種類型的所有產品）。
   • 我們的目標是最小化 x 的值（向任何商店提供的最多產品）。

2. 二分查找邏輯:

   • 對於每個中點 x，檢查是否可以分發所有產品，使得沒有商店擁有超過 x 個產品。
   • 使用輔助函數 canDistribute(x) 來決定可行性。

3. 可行性檢查（可以分發）：

   • 對於每種產品類型的數量，計算分銷該產品類型所需的最小商店數量，每個商店不得超過 x 個產品。
   • 對所有產品類型所需的商店進行求和。
   • 如果所需店舖總數小於或等於n，則可以以x作為每個店舖的最大負載進行分配；否則，這是不可行的。

4. 二分查找調整:

   • 如果 canDistribute(x) 傳回 true，則表示 x 是可行解，但我們想要最小化 x，因此調整右邊界。
   • 如果回傳 false，則增加左邊界，因為 x 太小。

5. 結果：

   • 二分查找完成後，left 將保存可能的最小 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. 效率：

   • 此解對於大輸入大小（n 和 m 高達 10^5）非常有效，因為二分搜尋的運行時間為 O(log(max_quantity) * m)，這在給定限制內是可行的。

這種方法最大限度地減少了 x，確保產品盡可能均勻地分佈在商店中。

聯絡連結

如果您發現本系列有幫助，請考慮在 GitHub 上給 存儲庫 一個星號或在您最喜歡的社交網絡上分享該帖子？ 。您的支持對我來說意義重大！

如果您想要更多類似的有用內容，請隨時關注我：

• 領英
• GitHub

以上是最小化分配到任何商店的產品數量的詳細內容。更多資訊請關注PHP中文網其他相關文章！