ORID36 binary search

[1011] Capacity to ship packages within D days

算法

用什么算法？
binary search
为什么用这个算法？
这道题给了你一组数组，然后问你取一个最小的shipping capacity（这个数不一定在数组里，甚至根本就不应该在数组里，除非数字很小）。要做什么呢？要把这组数当作converyor belt上面的货物，每个数字就是货物的重量，然后你需要在D天内把所有货物寄出去，实际上就是说你要把这数组分成D份，然后每份里面的和要小于你取的shipping capacity。比如说你的货物有[1,2,3,4,5,6,7,8,9,10] 然后你取了一个10000 shipping capacity的数。那一次就可以把整个数组装进去了。但我们要求最小的capacity，所以这里就可以用一个二分法来判断了。因为你有个判断条件。就是你在过这个数组的时候，你要count需要多少次才能运完。然后如果count <= D, 那么你当前的数就可以，那么end = mid;
否则，你猜的书就太小了，那么start = mid + 1;
代码：

    public static int shipWithinDays(int[] weights, int D) {
        int start = 0, end = 0;
        for (int i : weights) {
            start = Math.max(start, i);
            end += i;
        }
        while (start < end) {
            int mid = start + (end - start) / 2;
            int sum = 0, count = 1;
            for (int i = 0; i < weights.length; i++) {
                sum += weights[i];
                if (sum <= mid) {
                    continue;
                } else {
                    sum = 0;
                    count++;
                    --i;
                }
            }
            
            if (count <= D) {
                end = mid;
            } else {
                start = mid + 1;
            }
        }
        return start;
    }

代码实现

有什么要注意的地方？
这题我一开始老是TLE（time limited exception）， 因为我用了两个while loop，后来发现实际上一个for loop 就可以解决。我两个while loop是这么想的，第一个while loop 一直跑，直到第二个while loop 跑完，也就是所有数组里的数都被算完了。那么返回count，然后判断你的capacity是否达标。但实际上不用那么麻烦，你直接一个for loop就解决了，你再跑每个数的时候，你记录当前的sum，如果sum <= mid （你猜的capacity），那么继续。如果不是，那么就相当于超过了capacity，sum = 0 （重置当前sum，并且i--）因为i是你当前的指针，你加了当前的数之后就超标了，那么i就要-1。然后继续。这个if else判断里面都需要count++， 因为你要记录你分了多少次才把这批货物运完，这样好在之后判断你猜的数在什么范围。
把两个while 变成一个for loop之后我就不会TLE了。总之这道题我觉得很不错，是一个锻炼自己二分法的一道好题目。

有什么可以优化的地方？

我一开始取的值就是题目里面给出的范围，后来发现这个范围可以优化
目前Time complexity是O（log（sum））sum就是这个数组的和。因为你取的数组的范围是这个数组最大的数到他们的和之间。（这点是参考了上次老哥的范围，我觉得他取的这个值的范围很厉害，因为这避免了取值范围过大的问题，虽然在binary search上也不能省太多时间，但是还是很聪明的一个取值范围）。

时空复杂度

Time O(log(sum))
Space O(1) 没用占用任何新的空间

哪些相关题目做过的？

根koko吃香蕉，还有花束那两道题很像。都是一个数组里面找出符合条件最小的数。