[M二分]lc1760.袋子里最少数目的球(二分答案+数学推导+GoLang使用技巧)

文章目录 1. 题目来源2. 题目解析

1. 题目来源

链接：1760. 袋子里最少数目的球

题单：

待补充 2. 题目解析

思路：

看题意求最大、最小，很明显的二分答案，直接去二分满足条件下的最终袋子中球的个数。二段性思考： 如果最终袋子中球都是 1 个的话，那么袋子肯定很多，操作次数就非常多。如果最终袋子中球都可以装很多的时候，那么一开始都不用二分，操作次数就是 0。故，二分的边界点就是这个操作次数。那么操作边界就是最终袋子中能装的球的个数，即 [1, max{nums[0~n-1]}。 操作次数思考： 如果二分答案袋子中的球至多可装 y 个情况下。那么原有袋子球在 [1,y] 的操作次数是 0，在 [y+1, 2y] 的操作次数是 1。数学归纳来看，nums[i] 的操作次数就是 n u m s [ i ] − 1 y {\frac{nums[i]-1}{y}} ynums[i]−1​

综上，本题实际上不是很难，值得一提的是：

关于这个操作次数的推导，可以看看灵神那边针对边界、针对上取整、下取整的数学推导，更为严谨。可以看看官解中针对 1~y、y+1 ~2y 这种分段的判断，更为直观。最近拿 GoLang 写算法，比如二分，比如求 slice 中的最大元素，都有现成的库函数待学习。见这个博主的博文整理，挺不错的：【Go基础】Go算法常用函数整理

---

坑点：

C++ 选手记得开 long long 不然会爆…[1000000000,1000000000,1000000000] 1000000000 这个数据，最终结果是 3，但 cnt 的累计就很多很多超过 int 上限了…

---

时间复杂度： O ( n ) O(n) O(n)空间复杂度： O ( 1 ) O(1) O(1)

---

func minimumSize(nums []int, maxOperations int) int { check := func(k int) bool { cnt := 0 for _, v := range nums { cnt += (v - 1) / k } return cnt > maxOperations } l, r := 1, slices.Max(nums) for l < r { mid := (l + r) / 2 if check(mid) { l = mid + 1 } else { r = mid } } return l }

---

库函数写法：

func minimumSize(nums []int, maxOperations int) int { max := 0 for _, x := range nums { if x > max { max = x } } return sort.Search(max, func(y int) bool { if y == 0 { return false } ops := 0 for _, x := range nums { ops += (x - 1) / y } return ops <= maxOperations }) }