Leetcode-在 D 天内送达包裹的能力（中等）

题目描述

带上的包裹必须在 D 天内从一个港口运送到另一个港口。
传送带上的第 i 个包裹的重量为 weights[i]。每一天，我们都会按给出重量的顺序往传送带上装载包裹。我们装载的重量不会超过船的最大运载重量。
返回能在 D 天内将传送带上的所有包裹送达的船的最低运载能力。

输入：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

最低运载能力肯定是大于每个包裹的重量的，所以遍历找到最大值。
然后开始计算，以此值作为答案，需要的天数是否会超过需要的天数，超过时加大运载能力，小于等于时输出。

class Solution {
public:
    int shipWithinDays(vector<int>& weights, int D) {
        int v=0;
        for(auto i:weights)
            if(i>v) v=i;
        while(true){
            int temp=v,count=1;
            for(int i:weights){
                if(temp-i<0){
                    count++;
                    if(count>D) break;
                    temp=v;
                }
                temp-=i;
            }
            if(count<=D) break;//小于也可以，说明已绰绰有余
            v++;
        }
        return v;
    }
};

优化：
每个包裹的重量<最低运载能力<包裹总重量
即，包裹重量最大值<最低运载能力<包裹总重量
然后二分法，天数大于时向右看，天数向左时向左看，找到分界点。

class Solution {
public:
    int shipWithinDays(vector<int>& weights, int D) {
        int left=0,right=0;
        for(auto i:weights){
            if(i>left) left=i;
            right+=i;
        }
        while(left<right){
            int mid=(right-left)/2+left;
            if(cancarry(weights,D,mid)>D) 
                left=mid+1;
            else 
                right=mid;
        }
        return left;
    }
    int cancarry(vector<int>& weights,int D, int v){
        int count=1,temp=v;
        for(int i:weights){
            if(temp-i<0){
                count++;
                temp=v;
            }
            temp-=i;
        }
        return count;
    }
};