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%。我麻了。

​