###### tags: `LeetCode` `Medium` `Binary Search`
# LeetCode #1011 [Capacity To Ship Packages Within D Days](https://leetcode.com/problems/capacity-to-ship-packages-within-d-days/)
### (Medium)

傳送帶上的包裹必須在 D 天內從一個港口運送到另一個港口。

傳送帶上的第 i 個包裹的重量為 weights[i]。每一天，我們都會按給出重量的順序往傳送帶上裝載包裹。我們裝載的重量不會超過船的最大運載重量。

返回能在 D 天內將傳送帶上的所有包裹送達的船的最低運載能力。

---
左值為所有包裹中最重的重量(如果小於該重量則無論如何都沒有辦法運送該包裹), 右值則設為全部包裹重量總和。

每次判斷以中值作為船的運載重量, 當下一包裹的重量大於剩餘可運送的運載重量時, 則須將運送時間增加一天, 並將運載重量歸零, 再加上該包裹的重量。

若運送時間大於規定時間, 則代表單次運載量過低, 此時將左值改為中值+1, 反之則將右值改為中值。

---

class Solution {
public:
    int shipWithinDays(vector<int>& weights, int days) {
        int l=0, r=0;
        for(int w:weights){
            l=max(l, w);
            r+=w;
        }
        while(l<r){
            int m=l+(r-l)/2, d=1, cur=0;
            for(int w:weights){
                if(cur+w>m){
                    d++;
                    cur=0;
                }
                cur+=w;
            }
            if(d>days)l=m+1;
            else r=m;
        }
        return l;
    }
};