algo/di-yi-zhan-da78c/shou-ba-sh-48c1d/er-fen-sou-ae51e/

[giscus[bot]]

algo/di-yi-zhan-da78c/shou-ba-sh-48c1d/er-fen-sou-ae51e/

Info 数据结构精品课 (https://aep.h5.xeknow.com/s/1XJHEO) 和 递归算法专题课 (https://aep.xet.tech/s/3YGcq3) 限时附赠网站会员！第 21 期打卡挑战 (https://opedk.xet.tech/s/4ptSo2) 开始报名！ 读完本文，你不仅学会了算法套路，还可以顺便解决如下...

https://labuladong.gitee.io/algo/di-yi-zhan-da78c/shou-ba-sh-48c1d/er-fen-sou-ae51e/

[TrustTheProcess1024]

妙啊

[lizimu0709]

两端都闭的二分搜索似乎行不通，最后一个test case过不了

class Solution {
    public int minEatingSpeed(int[] piles, int H) {
        int left = 1;
        int right = 1000000000;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (f(piles, mid) <= H) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }

    int f(int[] piles, int x) {
        int hours = 0;
        for (int i = 0; i < piles.length; i++) {
            hours += piles[i] / x;
            if (piles[i] % x > 0) {
                hours++;
            }
        }
        return hours;
    }
}

piles =
[805306368,805306368,805306368]
h =
1000000000
Use Testcase
Output
1
Expected
3

[Yuxi-Zhang]

f funciton里hours的datatype换成long

[lqyspace]

将f的返回值类型和hours的数据类型换成long

[shiboys]

二分法的应用场景好强大，不过不太好找到这样的使用场景。总之，很好很强大！

[bad-mask]

服！

[renqHIT]

875. 爱吃香蕉的珂珂 | 力扣 | LeetCode
     // 中文网站和英文网站的超链接贴反了

[SkyeKD]

像410这种题目怎么想到和运送货物一样可以用二分搜索法的？害，看解析之前，我想半天也没把这两个联系起来

[RayInCode]

我觉得用二分搜索做410这个题似乎要注意采用的区间是开还是闭. 如果m在函数曲线中每有一个对应的整数x的话, 二分搜索搜索不到一个x满足f(x) = m. 这时候二分搜索停止在哪,以及最后返回的x是哪一个就需要注意了.
因此需要在返回结果的时候,判断一下当前的x * m 是否小于数组之和, 如果是的话x++, 否则x保持不变.

[RayInCode]

验证了一下,似乎不用担心这个问题, 也不用做额外的判断. 如果返回的是left的话, 无论开闭区间都能够得到正确的答案.
如果寻找x值不存在,则无论开闭区间, left都会停在偏右侧, 这和本题的要求正好相符合.

[CZT0]

NB

[ImZzBy]

对于leetcode1011题，为了尽可能多的装货物，需要频繁对weights数组进行区间求和，那能不能用个前缀和，减少求和次数