给你一个整数 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 <= 105
1 <= quantities[i] <= 105
方法一:二分查找
我们注意到,如果分配给任意商店商品数目的最大值为
我们定义二分查找的左边界
二分查找结束后,答案即为
时间复杂度
class Solution:
def minimizedMaximum(self, n: int, quantities: List[int]) -> int:
def check(x):
return sum((v + x - 1) // x for v in quantities) <= n
return 1 + bisect_left(range(1, 10**6), True, key=check)
class Solution {
public int minimizedMaximum(int n, int[] quantities) {
int left = 1, right = (int) 1e5;
while (left < right) {
int mid = (left + right) >> 1;
int cnt = 0;
for (int v : quantities) {
cnt += (v + mid - 1) / mid;
}
if (cnt <= n) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
}
class Solution {
public:
int minimizedMaximum(int n, vector<int>& quantities) {
int left = 1, right = 1e5;
while (left < right) {
int mid = (left + right) >> 1;
int cnt = 0;
for (int& v : quantities) {
cnt += (v + mid - 1) / mid;
}
if (cnt <= n) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
};
func minimizedMaximum(n int, quantities []int) int {
return 1 + sort.Search(1e5, func(x int) bool {
x++
cnt := 0
for _, v := range quantities {
cnt += (v + x - 1) / x
}
return cnt <= n
})
}
function minimizedMaximum(n: number, quantities: number[]): number {
let left = 1;
let right = 1e5;
while (left < right) {
const mid = (left + right) >> 1;
let cnt = 0;
for (const v of quantities) {
cnt += Math.ceil(v / mid);
}
if (cnt <= n) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}