Leetcode上「Koko 吃香蕉」和 「货物运输」是通过二分搜索来确定边界的经典场景。
- Leetcode 875
显然最少为 1,最大为max(piles)
,因为一小时最多只能吃一堆香蕉。那么暴力解法就很简单了,只要从 1 开始穷举到max(piles)
,一旦发现发现某个值可以在H
小时内吃完所有香蕉,这个值就是最小速度:
int minEatingSpeed(vector<int>& piles, int H) {
// piles 数组的最大值
int max = getMax(piles);
for (int speed = 1; speed < max; speed++) {
// 以 speed 是否能在 H 小时内吃完香蕉
if (canFinish(piles, speed, H))
return speed;
}
return max;
}
由于我们要求的是最小速度,所以可以用一个搜索左侧边界的二分查找来代替线性搜索,提升效率:
int minEatingSpeed(vector<int>& piles, int H) {
// 套用搜索左侧边界的算法框架,左闭右开
int left = 1, right = getMax(piles) + 1;
while (left < right) {
// 防止溢出
int mid = left + (right - left) / 2;
if (canFinish(piles, mid, H)) {
right = mid;
} else {
left = mid + 1;
}
}
return left;//左边界
}
canFinish不太好写:
bool canFinish(vector<int>& piles, int speed, int Hour){
int need=0;
for(int i=0;i<piles.size();++i){
need+=(piles[i]/speed+piles[i]%speed?1:0);
}
return need<=Hour;
}
- Leetcode 1011
**
要在D
天内运输完所有货物,货物不可分割,最终确定运输的最小载重(下文称为cap
):
本质上和 Koko 吃香蕉的问题一样的,首先确定cap
的最小值和最大值分别为max(weights)
和sum(weights)
。
int shipWithinDays(vector<int>& weights, int D) {
//默写出二分搜索的框架
//约定二分搜索策略为:左闭右开
int left = getMax(weights);// 载重可能的最小值
int right = getSum(weights) + 1;// 载重可能的最大值 + 1
while (left < right) {
int mid = left + (right - left) / 2;
if (canFinish(weights, D, mid)) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
canFinish同样不太好写:
bool canFinish(vector<int>& weights, int Day, int paylaod){
int i=0;
int needDay=0;
while(i!= weights.size()){
int sum=0;
while(sum+weights[i]<=payload){
sum+=weights[i];
++i;
}
needDay++;
}
return needDay<=Day;
}
这题和画匠问题是一个意思:
这里画匠数量就是上一题中的Day,确定画作的最少时间就是上一题中的轮船的最小payload。