1011. Capacity To Ship Packages Within D Days (M)

https://leetcode.com/problems/capacity-to-ship-packages-within-d-days/

A conveyor belt has packages that must be shipped from one port to another within days days.

The ith package on the conveyor belt has a weight of weights[i]. Each day, we load the ship with packages on the conveyor belt (in the order given by weights). We may not load more weight than the maximum weight capacity of the ship.

Return the least weight capacity of the ship that will result in all the packages on the conveyor belt being shipped within days days.

Example 1:

Input: weights = [1,2,3,4,5,6,7,8,9,10], days = 5
Output: 15
Explanation: A ship capacity of 15 is the minimum to ship all the packages in 5 days like this:
1st day: 1, 2, 3, 4, 5
2nd day: 6, 7
3rd day: 8
4th day: 9
5th day: 10

Note that the cargo must be shipped in the order given, so using a ship of capacity 14 and splitting the packages into parts like (2, 3, 4, 5), (1, 6, 7), (8), (9), (10) is not allowed.

Example 2:

Input: weights = [3,2,2,4,1,4], days = 3
Output: 6
Explanation: A ship capacity of 6 is the minimum to ship all the packages in 3 days like this:
1st day: 3, 2
2nd day: 2, 4
3rd day: 1, 4

Example 3:

Input: weights = [1,2,3,1,1], days = 4
Output: 3
Explanation:
1st day: 1
2nd day: 2
3rd day: 3
4th day: 1, 1

Constraints:

• 1 <= days <= weights.length <= 5 * 104

• 1 <= weights[i] <= 500

Solution:

https://mp.weixin.qq.com/s/JgJ0jh2SJd6grQSPnN6Jww

要在D天内按顺序运输完所有货物，货物不可分割，如何确定运输的最小载重呢？

函数签名如下：

int shipWithinDays(int[] weights, int days);

和上一道题一样的，我们按照流程来就行：

1、确定x, f(x), target分别是什么，并写出函数f的代码。

题目问什么，什么就是自变量，也就是说船的运载能力就是自变量x。

运输天数和运载能力成反比，所以可以让f(x)计算x的运载能力下需要的运输天数，那么f(x)是单调递减的。

函数f(x)的实现如下：

// 定义：当运载能力为 x 时，需要 f(x) 天运完所有货物
// f(x) 随着 x 的增加单调递减
int f(int[] weights, int x) 
{    
    int days = 0;    
    for (int i = 0; i < weights.length; ) 
    {        
        // 尽可能多装货物        
        int cap = x;        
        while (i < weights.length) 
        {            
            if (cap < weights[i]) break;            
            else cap -= weights[i];            
            i++;        
        }        
        days++;    
    }    
    return days;
}

Another Version:
 public int totalTime(int[] weights, int cap)
    {
        int days = 1;
        int sum = 0;
        for(int i = 0; i< weights.length; i++)
        {
            if(sum + weights[i] <=cap)
            {
                sum += weights[i];
            }
            else
            {
                sum = weights[i];
                days++;
            }
        }
        return days;
    }

对于这道题，target显然就是运输天数D，我们要在f(x) == D的约束下，算出船的最小载重。

2、找到x的取值范围作为二分搜索的搜索区间，初始化left和right变量。

船的最小载重是多少？最大载重是多少？

显然，船的最小载重应该是weights数组中元素的最大值，因为每次至少得装一件货物走，不能说装不下嘛。!!!

最大载重显然就是weights数组所有元素之和，也就是一次把所有货物都装走。

3、需要根据题目的要求，确定应该使用搜索左侧还是搜索右侧的二分搜索算法，写出解法代码。

现在我们确定了自变量x是船的载重能力，f(x)是单调递减的函数，target就是运输总天数限制D，题目要我们计算船的最小载重，也就是x要尽可能小：

到这里，这道题的解法也写出来了，我们合并一下多余的 if 分支，提高代码运行速度，最终代码如下：

class Solution {
    public int shipWithinDays(int[] weights, int days) {
        
        int start = 1;
        int end = 0;
            
        for(int i = 0; i< weights.length; i++)
        {
            start = Math.max(start, weights[i]);
            end += weights[i];
        }
        
        while(start+1<end)
        {
            int mid = start+(end-start)/2;
            if(totalTime(weights, mid) <= days)
            {
                end=mid;
            }
            else 
            {
                start = mid;
            }
        }
        
        if(totalTime(weights, start) <= days) return start;
        if(totalTime(weights, end) <= days) return end;
        
        return -1;
        
    }
    
    public int totalTime(int[] weights, int cap)
    {
        int days = 1;
        int sum = 0;
        for(int i = 0; i< weights.length; i++)
        {
            if(sum + weights[i] <=cap)
            {
                sum += weights[i];
            }
            else
            {
                sum = weights[i];
                days++;
            }
        }
        return days;
    }
}

本文就到这里，总结来说，如果发现题目中存在单调关系，就可以尝试使用二分搜索的思路来解决。搞清楚单调性和二分搜索的种类，通过分析和画图，就能够写出最终的代码