题目

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

思路

首先理解题目的意思:

按照数组的顺序分组，分成D个组，每组的和的最小值，这样的想法是求分组每组和的最小值的，但是其实这样的思路并不能很好的求解。

此类题目还可以采用这样的思路 通常我们会去联合「答案」去想解法 （from 三叶姐）

参考了题解，这个题目竟然可以用二分搜索，怎么搜索呢？ 可以直接从题目所给的范围搜索 

我觉得也可以理解为暴力的优化，

• 1 <= D <= weights.length <= 5 * 104
• 1 <= weights[i] <= 500

为什么可以使用二分搜索，二分搜索的目标是ans，也就是船的最小运载量，在ans可能的范围里，具有二段性，

其实就是求满足条件（条件是这个运载量可以满足题意）的左边界

 不满足条件             满足条件

【—————|——————————】

             船的最小运载量

假定「D 天内运送完所有包裹的最低运力」为 ans，那么在以 ans 为分割点的数轴上具有「二段性」：

数值范围在(−∞,ans) 的运力必然「不满足」 D 天内运送完所有包裹的要求
数值范围在 [ans,+∞) 的运力必然「满足」 D天内运送完所有包裹的要求

作者：AC_OIer
链接：https://leetcode-cn.com/problems/capacity-to-ship-packages-within-d-days/solution/gong-shui-san-xie-li-yong-er-duan-xing-z-95zj/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

满足条件的check函数

check函数输入是运力 cap 和 题目所给的条件

判断是否能在d天内运送完所有的包裹

代码

bool check(vector<int>& weights, int D,int cap){
    int n = weights.size();
    int num = 0;
    int t = 0;
    for(int i=0;i<n;){
        if(weights[i]>cap){
            return false;
        }
        //按顺序装上船
        while(i<n && t+weights[i]<=cap){
            t = t+weights[i];
            i++;
        }
        num++;
        t=0;
    }
    return num<=D;

}
int shipWithinDays(vector<int>& weights, int D) {
    //二分搜索 直接搜索ans
    int left = 1;
    int right = 1e8;
    while(left<right){   //最后退出的时候是等于
        int mid = left+right>>1;
        if(check(weights,D,mid)){
            right = mid;
        }else{
            left = mid+1;
        }
    }
    return left;
}

延伸题目