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

传送带上的包裹必须在 D 天内从一个港口运送到另一个港口。

传送带上的第 i 个包裹的重量为 weights[i]。每一天，我们都会按给出重量的顺序往传送带上装载包裹。我们装载的重量不会超过船的最大运载重量。

返回能在 D 天内将传送带上的所有包裹送达的船的最低运载能力。

二分法

思路

「在…限定条件内求取最小or最大值」是二分搜索题目常见的问法。
我们设定一个运载量x,以该运载量传送所有包裹需要y天，若出现如下情况。

• y<=D,说明运载量x可能设置大了，保存该x，并把右边界设为x-1;
• y>D，说明运载量x设置小了，左边界设置为x+1

对于边界的设定。显然左边界lhs=max(weight),右边界rhs=sum(weight);

实现

class Solution {
public:
    int shipWithinDays(vector<int>& weights, int D) {
        int l=1,r=0,ans=0;
        for(auto v:weights){
            r+=v;
            if(l<v) l=v;
        }
        while(l<=r){
            int mid=l+((r-l)>>1);
            if(istrue(weights,D,mid)){
                r=mid-1;
                ans=mid;
            }
            else{
                l=mid+1;
            }
        }
        return ans;
    }
    bool istrue(vector<int>& weights,int D,int carry){
        int cnt=1,curSum=0;
        for(auto v:weights){
            curSum+=v;
            if(curSum>carry){
                curSum=v;
                cnt++;
            }
        }
        return cnt<=D;
    }
};

复杂度分析

• 时间复杂度:
• 空间复杂度:

☆☆875. 爱吃香蕉的珂珂

珂珂喜欢吃香蕉。这里有 N 堆香蕉，第 i 堆中有 piles[i] 根香蕉。警卫已经离开了，将在 H 小时后回来。

珂珂可以决定她吃香蕉的速度 K （单位：根/小时）。每个小时，她将会选择一堆香蕉，从中吃掉 K 根。如果这堆香蕉少于 K 根，她将吃掉这堆的所有香蕉，然后这一小时内不会再吃更多的香蕉。

珂珂喜欢慢慢吃，但仍然想在警卫回来前吃掉所有的香蕉。

返回她可以在 H 小时内吃掉所有香蕉的最小速度 K（K 为整数）。

• 1 <= piles.length <= 10^4
• piles.length <= H <= 10^9
• 1 <= piles[i] <= 10^9

思路

「在…限定条件内求取最小or最大值」是二分搜索题目常见的问法。
我们设定一个速度x,以该速度吃香蕉需要cnt小时，若出现如下情况。

• cnt<=H,吃的太快，说明x可能设置大了，保存该x，并把右边界设为x-1;
• cnt>H，吃的太慢,说明速度x设置小了，左边界设置为x+1

对于边界的设定。显然左边界lhs=1,右边界rhs=1e9;

算法

如何求得y？
对于piles[i],吃掉它需要的时间为t=piles[i]/x+(piles[i]%x!=0);故总时间为循环叠加！

实现

class Solution {
public:
    int minEatingSpeed(vector<int>& piles, int H) {
        int l=1,r=1e9,ans=0;
        int n=piles.size();
        while(l<=r){
            long mid=l+((r-l)>>1);
            if(ifFinish(piles,H,mid)){
                ans=mid;
                r=mid-1;
            }
            else{
                l=mid+1;
            }
        }
        return ans;
    }
    bool ifFinish(vector<int>& piles, int H,long k){
        long cnt=0;
        for(auto val:piles){
            cnt+=val/k+(val%k!=0);
        }
        return cnt<=H;
    }

复杂度分析

• 时间复杂度:
• 空间复杂度:

题目标题难度划分

算法掌握难度程度划分