分配给商店的最多商品的最小值

难度: Medium

给你一个整数 n ，表示有 n 间零售商店。总共有 m 种产品，每种产品的数目用一个下标从 0 开始的整数数组 quantities 表示，其中 quantities[i] 表示第 i 种商品的数目。

你需要将 所有商品 分配到零售商店，并遵守这些规则：

一间商店至多只能有 一种商品 ，但一间商店拥有的商品数目可以为任意件。
分配后，每间商店都会被分配一定数目的商品（可能为 0 件）。用 x 表示所有商店中分配商品数目的最大值，你希望 x 越小越好。也就是说，你想 最小化 分配给任意商店商品数目的 最大值 。

请你返回最小的可能的 x 。

示例 1：

输入：n = 6, quantities = [11,6]
输出：3
解释： 一种最优方案为：
- 11 件种类为 0 的商品被分配到前 4 间商店，分配数目分别为：2，3，3，3 。
- 6 件种类为 1 的商品被分配到另外 2 间商店，分配数目分别为：3，3 。
分配给所有商店的最大商品数目为 max(2, 3, 3, 3, 3, 3) = 3 。

示例 2：

输入：n = 7, quantities = [15,10,10]
输出：5
解释：一种最优方案为：
- 15 件种类为 0 的商品被分配到前 3 间商店，分配数目为：5，5，5 。
- 10 件种类为 1 的商品被分配到接下来 2 间商店，数目为：5，5 。
- 10 件种类为 2 的商品被分配到最后 2 间商店，数目为：5，5 。
分配给所有商店的最大商品数目为 max(5, 5, 5, 5, 5, 5, 5) = 5 。

示例 3：

输入：n = 1, quantities = [100000]
输出：100000
解释：唯一一种最优方案为：
- 所有 100000 件商品 0 都分配到唯一的商店中。
分配给所有商店的最大商品数目为 max(100000) = 100000 。

提示：

m == quantities.length
1 <= m <= n <= 10⁵
1 <= quantities[i] <= 10⁵

Submission

运行时间: 522 ms

内存: 27.5 MB

class Solution:
    def minimizedMaximum(self, n: int, quantities: List[int]) -> int:
        l, r = 1, max(quantities) + 1
        while l < r:
            mid = (l + r) // 2
            if sum([(i - 1) // mid + 1 for i in quantities]) < n + 1:
                r = mid
            else:
                l = mid + 1
        return l

Explain

此题解采用二分查找的方法来解决问题。二分查找的目标是找到最小的x，使得商品的最大分配数目尽可能小。初始化左右边界l和r，其中l为1（至少一个商品分配给一家商店），r为quantities数组中的最大值加一（最大可能的分配数目）。在每次迭代中，计算中间值mid作为当前试探的最大分配数目。通过计算每种商品至少需要多少家商店来容纳（每种商品数量除以mid，向上取整），如果总需要的商店数小于等于n，则说明可以尝试更小的x，更新右边界r。如果总需要的商店数大于n，则需要增大x，更新左边界l。最终，左边界l将表示最小的可能的x。

时间复杂度: O(m * log(max(quantities)))

空间复杂度: O(1)

# 分配给商店的最多商品的最小值的解决方案
class Solution:
    def minimizedMaximum(self, n: int, quantities: List[int]) -> int:
        l, r = 1, max(quantities) + 1 # 初始化左右边界
        while l < r: # 二分查找
            mid = (l + r) // 2 # 计算中点作为当前的最大商品数
            # 计算所有商品以mid为最大分配数量时，需要的商店总数
            if sum([(i - 1) // mid + 1 for i in quantities]) < n + 1:
                r = mid # 如果商店数较少，尝试更小的mid
            else:
                l = mid + 1 # 否则尝试更大的mid
        return l # 返回最小可能的最大分配数

Explore

在二分搜索中，左边界l初始化为1是因为至少需要将一个商品分配给一家商店，即一个商店至少分配一个商品是最小的可能情况。右边界r初始化为quantities中的最大值加一是为了确保在二分搜索的过程中可以覆盖到所有可能的最大商品分配数目的情况。由于右边界是开区间，故加一确保包含最大商品数量的情况在考虑范围内。

在二分搜索中，为了计算每种商品所需的商店数量，采用了向上取整的方法。具体计算方式是：对于每种商品的数量i，计算i除以当前mid（考虑的最大商品分配数目），然后向上取整。这可以通过公式(i - 1) // mid + 1来实现，其中(i - 1) // mid计算i除以mid后向下取整的结果，加1是为了处理不能整除的情况，确保所有商品都能被分配。

使用`sum([(i - 1) // mid + 1 for i in quantities]) < n + 1`确实有误，应该使用`<= n`来判断。这里的目标是检查所有商品总共需要的商店数量是否不超过n个商店。如果使用`< n + 1`，实际上是错误地将条件放宽了，允许的商店数量比实际可用的商店多一个，这是不正确的。正确的判断应是`sum([(i - 1) // mid + 1 for i in quantities]) <= n`，确保商店数量不超过n。

在二分搜索中，如果计算得到的总商店需求小于等于n，说明当前的mid可能还过大，可以分配的商品数目可能还能更小，因此更新右边界r为mid，以缩小搜索区间，寻找更小的可能值。相反，如果总需求超过n，说明当前的mid太小，分配给每个商店的商品数目不足以满足所有商品的分配，需要增大mid，因此更新左边界l为mid + 1，以增大商品的分配数目。这样的更新策略确保了二分搜索能逐步逼近最优解。