2021-4-26 力扣每日一题

1011在D天内送达包裹的能力

问题描述：

​ 传送带上的包裹必须在 D 天内从一个港口运送到另一个港口。

​ 传送带上的第 i 个包裹的重量为 weights[i]。每一天，我们都会按给出重量的顺序往传送带上装载包裹。我们装载的重量不会超过船的最大运载重量。

​ 返回能在 D 天内将传送带上的所有包裹送达的船的最低运载能力。

示例1：

输入：weights = [1,2,3,4,5,6,7,8,9,10], D = 5
输出：15
解释：
船舶最低载重 15 就能够在 5 天内送达所有包裹，如下所示：
第 1 天：1, 2, 3, 4, 5
第 2 天：6, 7
第 3 天：8
第 4 天：9
第 5 天：10

请注意，货物必须按照给定的顺序装运，因此使用载重能力为 14 的船舶并将包装分成 (2, 3, 4, 5), (1, 6, 7), (8), (9), (10) 是不允许的。 
           

示例2：

输入：weights = [3,2,2,4,1,4], D = 3
输出：6
解释：
船舶最低载重 6 就能够在 3 天内送达所有包裹，如下所示：
第 1 天：3, 2
第 2 天：2, 4
第 3 天：1, 4
           

示例3：

输入：weights = [1,2,3,1,1], D = 4
输出：3
解释：
第 1 天：1
第 2 天：2
第 3 天：3
第 4 天：1, 1
           

思路:

方法一（贪心）

​ 首先最容易想到的思路就是枚举了，当然我们这里贯彻这样的思路，将枚举进行到底！！

​ 当然了，枚举也不能随便枚举，我们要枚举得有智慧，很容易我们可以得到，运的最小吨位不能小于数列的最大值，不然肯定运不走，所以我们就从最大值开始遍历即可。

• 当结果大于目标值的时候，我们就将暂时的和设为当前的值。并将天数减一
• 当结果等于目标值的时候。
  • 可能我们的货还没有装完，这时将暂时的和设置为0，天数减一即可
  • 可能我们的货已经装完了，此时i = n-1，这时返回当前的目标值即可
• 最后，我们进行一个判断，我们是因为天数等于0了，跳出循环，则将目标值+1，重复此过程
• 当不是因为天数为0跳出循环，则返回我们的目标值即可

Java代码

/**
* @Description: 力扣1011题题解
* @return: 返回结果
* @Author: Mr.Gao
* @Date: 2021/4/26
*/

public int shipWithinDays(int[] weights, int D) {
    int sum = 0;
    int n = weights.length;
    int min = Integer.MIN_VALUE;
    for (int i = 0; i < n; i++) {
        sum+=weights[i];
        if(weights[i]>min){
            min = weights[i];
        }
    }
    int re = Math.max((int)((sum+0.5)/D),min);
    int k = D;
    while(true){
        int temp = 0;
        boolean flag = false;
        for (int i = 0; i < n; i++) {
            temp+=weights[i];
            if(temp==re){
                temp = 0;
                k--;
                if(k==0){
                    if(i==n-1){
                        return re;
                    }
                    re++;
                    flag=true;
                    break;
                }
            } else if(temp>re){
                temp = weights[i];
                k--;
                if(k==0){
                    re++;
                    flag=true;
                    break;
                }
            }
        }
        k = D;
        temp = 0;
        if(!flag){
            return re;
        }
    }
}
           

​ 结果是什么，一顿操作猛如虎，提交一看5%，虽然吧，但是5%太也拉了吧

方法二【二分+贪心】（官方题解）

​ 其实贪心策略和上方基本相同，但是在查找目标值的时候，多用了一个二分。优化的地方在于，我们的结果一定是在某个区间里的，最小不能小于数列中的最大值，最大不能大于数列的元素和，所以我们在这个区间里进行二分查找，找到符合标准的值即可，上面的有点拉胯，是因为上面在找目标值的时候，用的是顺序查找，如果换成二分，可能会有所不同哦。

Java代码：

public int shipWithinDays(int[] weights, int D) {
    // 确定二分查找左右边界
    int left = Arrays.stream(weights).max().getAsInt(), right = Arrays.stream(weights).sum();
    
    while (left < right) {
        int mid = (left + right) / 2;
        // need 为需要运送的天数
        // cur 为当前这一天已经运送的包裹重量之和
        int need = 1, cur = 0;
        for (int weight : weights) {
            if (cur + weight > mid) {
                ++need;
                cur = 0;
            }
            cur += weight;
        }
        if (need <= D) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return left;
}
           

• 果然题解的高度是我达不到的，贪心的那一段真的把我看呆了，原来可以这么写，可能我也可以这么写，但是这种简洁程度真的。哎，加油吧！！

  

• 题解才13.44%。我麻了。

​