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
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 42.73.100.10 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1731594941.A.9F7.html