本人参考yxc-y总的刷题课，总结了二分查找的两个模板：HERE
本专题为二分查找算法的应用——二分答案

LeetCode 875. 爱吃香蕉的珂珂

题目

思路

因为当k很大时，一定能在h小时内完成，因此答案可以进行二分。

二分答案：找右区间的左端点，即 【在 h 小时内吃掉所有香蕉的最小速度 k】。只需要计算吃掉所有香蕉所需要的时间sum，如果sum <= h 说明速度太快，需要降低速度(r = mid)，sum > h 说明速度太慢，时间太久，需要提高速度k（mid = l + 1）。

代码

class Solution {
public:
    bool check(vector<int>& piles, int h, int k){
        int sum = 0;
        for(int i = 0; i < piles.size(); i++){
            sum += piles[i] / k;
            if(piles[i] % k) sum++;
        }
        // cout << sum << " " << k << endl;
        // 二分答案：找右区间的左端点
        if(sum > h) return true; // 如果时间多了，就让速度k提高，否则降低速度k
        return false;
    }
    int minEatingSpeed(vector<int>& piles, int h) {
        int l = 1, r = 1e9+1;
        while(l < r){
            int mid = l + ((r - l) >> 1); // 需要加括号, 因为'+'优先级大于'>>'
            if(check(piles, h, mid)) l = mid + 1;
            else r = mid;
        }
        return l;
    }
};

LeetCode 2187. 完成旅途的最少时间

题目 示例

【返回完成 至少 totalTrips 趟旅途需要花费的 最少 时间】
输入：time = [1,2,3], totalTrips = 5
输出：3
解释：
- 时刻 t = 1 ，每辆公交车完成的旅途数分别为 [1,0,0] 。
  已完成的总旅途数为 1 + 0 + 0 = 1 。
- 时刻 t = 2 ，每辆公交车完成的旅途数分别为 [2,1,0] 。
  已完成的总旅途数为 2 + 1 + 0 = 3 。
- 时刻 t = 3 ，每辆公交车完成的旅途数分别为 [3,1,1] 。
  已完成的总旅途数为 3 + 1 + 1 = 5 。
所以总共完成至少 5 趟旅途的最少时间为 3 。

时间越多，可以完成的旅途也就越多，因此答案可以二分。

代码

class Solution {
typedef long long LL;
public:
    bool check(vector<int>& time, int totalTrips, LL mid){
        LL sum = 0;
        for(int i = 0; i < time.size(); i ++){
            sum += (mid / (LL)time[i]);
            if(sum >= totalTrips) return false;
        }
        return true;
    }

    LL minimumTime(vector<int>& time, int totalTrips) {
        LL l = 1, r = LLONG_MAX;
        while(l < r){
            LL mid = l + ((r - l) >> 1);
            if(check(time, totalTrips, mid)) l = mid + 1;
            else r = mid;
        }
        return l;
    }
};

LeetCode 6325. 修车的最少时间

题目 示例

输入：ranks = [4,2,3,1], cars = 10
输出：16
解释：
- 第一位机械工修 2 辆车，需要 4 * 2 * 2 = 16 分钟。
- 第二位机械工修 2 辆车，需要 2 * 2 * 2 = 8 分钟。
- 第三位机械工修 2 辆车，需要 3 * 2 * 2 = 12 分钟。
- 第四位机械工修 4 辆车，需要 1 * 4 * 4 = 16 分钟。
16 分钟是修理完所有车需要的最少时间。

思路

如果可以用 t 分钟修完所有车，那么同样可以用大于 t 分钟的时间修完所有车。
如果无法用 t 分钟修完所有车，那么同样无法用小于 t 分钟的时间修完所有车。
有单调性，可以二分答案。

代码

class Solution {
public:
    bool check(vector<int>& ranks, int cars, long long time){
        long long sum = 0;
        for(int i = 0; i < ranks.size(); i++){
            sum += (sqrt(time / (long long)ranks[i]));
            // cout << time << " " << sum << endl;
            if(sum >= cars) return false;
        }
        return true;
    }
    long long repairCars(vector<int>& ranks, int cars) {
        long long l = 1, r = LLONG_MAX;
        while(l < r){
            long long mid =  l + ((r-l) >> 1);
            // 找右区间的左端点
            if(check(ranks, cars, mid)) l = mid+1;
            else r = mid;
        }
        return l;
    }
};

LeetCode 2226. 每个小孩最多能分到多少糖果

题目 示例

输入：candies = [5,8,6], k = 3
输出：5
解释：可以将 candies[1] 分成大小分别为 5 和 3 的两堆，
然后把 candies[2] 分成大小分别为 5 和 1 的两堆。现在就有五堆大小分别为 5、5、3、5 和 1 的糖果。
可以把 3 堆大小为 5 的糖果分给 3 个小孩。可以证明无法让每个小孩得到超过 5 颗糖果。

代码

class Solution {
typedef long long LL;
public:
   int maximumCandies(vector<int>& candies, LL k) {
       LL l = 0, r = 1e12+1;
       while(l < r){
           // 找左区间的右端点
           LL mid = l + ((r - l + 1) >> 1);
           LL cnt = 0;
           for(auto x : candies) cnt += x / mid;
           if(cnt >= k) l = mid;
           else r = mid - 1;
       }
       return l;
   }
};