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

目录

• LeetCode 875. 爱吃香蕉的珂珂
• LeetCode 2187. 完成旅途的最少时间
• LeetCode 6325. 修车的最少时间
• LeetCode 2226. 每个小孩最多能分到多少糖果

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提高，否则降低速度kreturn 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;}
};

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！