2064. Minimized Maximum of Products Distributed to Any Store
有n个零售商
m种不同的商品
quantities矩阵表示每种商品的数量
必须把所有商品分配给零售商
而且每一个零售商只能拿一种商品
在分配完所有商品后
假设x是单一零售商拿到最多的商品数量
请问最小的x为多少?
思路:
假设quantities中最大的数字为max
那这题就是在1~max的区间进行二分搜寻法
找出满足条件的最小x值
大概是这样
golang code :
func minimizedMaximum(n int, quantities []int) int {
l, r := 1, slices.Max(quantities)
for r > l {
m := l + (r-l)/2
if canDistribute(m, quantities, n) {
r = m
} else {
l = m + 1
}
}
return l
}
func canDistribute(num int, quantities []int, n int) bool {
cnt := 0
for _, val := range quantities {
quotient := val / num
if val%num == 0 {
cnt += quotient
} else {
cnt += quotient + 1
}
if cnt > n {
return false
}
}
return true
}