最小化分配到任何商店的产品数量

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
  • 类型 1 的 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中文网其他相关文章！