Day70 | 灵神 | 二分查找：完成旅途的最少时间

2187.完成旅途的最少时间

2187. 完成旅途的最少时间 - 力扣（LeetCode）

思路

1.单调性判断二分谁

本题还是和前两天的那两道题一样，我们平分的还是时间

从单调性来讲，如果t的时间可以正好完成旅途，那么t+1，t+2的时间一定也可以

但是t-1就不行了，我们就是要找这样的t

2.求出二分区间

现在我们首先要做的就是求出我们的二分区间，即时间t的范围

笔者的思路是，找到单次旅途时间最短的车，然后乘以totalTrips，那这样也不用管别的车跑了几次，因为只需要这一辆车就可以跑够totalTrips，所以这是一个最大值

最小值不用思考了，那当然就是1了

注：这里最大值最小值灵神有个优化，感兴趣可以自行查看

2187. 完成旅途的最少时间 - 力扣（LeetCode）

3.写出判断条件即check函数

判断条件就是所有的车在t的时间内完成的所有旅程数量能否达到totalTrips

那么所有车在t的时间内完成的所有旅程数量怎么计算？

一辆车的旅程其实就是总时间t除以单次时间time[i]，而且是下取整，所以我们不需要做过多的处理

到这里就可以开始写代码了

完整代码

class Solution {
public:
    bool check(vector<int>& time, int totalTrips,long long t)
    {
        long long res=0;
        for(int c:time)
        {
            res+=(t/c);
            if(res>=totalTrips)
                return true;
        }
        return false;
    }
    long long minimumTime(vector<int>& time, int totalTrips) {
        long long min_time=ranges::min(time);
        long long l=1,r=min_time*totalTrips+1;
        while(l<r)
        {
            long long mid=l+(r-l)/2;
            if(check(time,totalTrips,mid))
                r=mid;
            else
                l=mid+1;
        }
        return l;
    }
};

注意

如果你卡在了116/124，即第116个例子左右，那你一定要看看该改long long的地方改没改

特别是传入check函数的t，那个形参的类型必须得是long long，笔者改了这个就通过了