1014. Capacity To Ship Packages Within D Days 运输最小容量

每天只能按顺序运送重 weight[i] 的物资，运输D天，求传送带的最小承重量最小承重量为最重的那一个物资最大承重量为所有物资的和，因为 D 至少可以为 1

这里有一个连续的搜索范围，妙用二分搜索来大幅降低搜索域，取容量为平均数，如果运送的天数大于 D，说明容量小了，如果小于D，说明容量大了

int shipWithinDays(vector<int>& weights, int D) {
    int max=weights[0];
    int sum=0;
    for(auto n : weights) {
        if (n>max) max=n;
        sum+=n;
    }

    int start=max;
    int end=sum;
    while(start<end) {
        int mid=(start+end)>>1;
        int ds=ship(weights, mid, D);
        if (ds > 0) start=mid+1;
        else end=mid;
    }
    return start;
}

int ship(vector<int> &w, int cap, int d, int cur=0, int curd=1) {
    for(auto n : w) {
        cur+=n;
        if (cur>cap) {
            cur=n;
            ++curd;
			// 大于D，提前结束
            if (curd>d) return 1;
        }
    }
    return curd-d;
}

#二分

1004. Max Consecutive Ones III 1018. Binary Prefix Divisible By 5