leetcode 875: 珂珂喜欢吃香蕉。这里有 n 堆香蕉,第 i 堆中有 piles[i] 根香蕉。警卫已经离开了,将在 h 小时后回来。
珂珂可以决定她吃香蕉的速度 k (单位:根/小时)。每个小时,她将会选择一堆香蕉,从中吃掉 k 根。如果这堆香蕉少于 k 根,她将吃掉这堆的所有香蕉,然后这一小时内不会再吃更多的香蕉。
珂珂喜欢慢慢吃,但仍然想在警卫回来前吃掉所有的香蕉。
返回她可以在 h 小时内吃掉所有香蕉的最小速度 k(k 为整数)。
看完题目之后可能很难联想到解决问题需要用到二分搜索,但是我们可以这样想,实际应用中,我们很难碰到一种情况,即把可能的答案列出来,还排好序,我们在这里面找到满足需求的target答案
,一般来说,我们可能有一个target这是我们需要达到的目标,此外可能如同函数一样可能的答案与结果target存在一种映射关系,f(x)
,x代表了我们的搜索空间,不同的x映射了不同的结果,而我们的目标就是找到满足target的x,严格来说满足target的x可能有无数个,但是题目一般会限定最大OR最小
,而f(x)一般就是题目所给的规则,这个f(x)一般需要自己去抽象出来。比如本题:
// 定义:速度为 x 时,需要 f(x) 小时吃完所有香蕉
// f(x) 随着 x 的增加单调递减
int f(vector<int>& piles, int x) {
int hours = 0;
for (int i = 0; i < piles.size(); i++) {
hours += piles[i] / x;
if (piles[i] % x > 0) {
hours++;
}
}
return hours;
}
对于f(x)的抽象应该是这种题目的一个难点,需要仔细阅读题目,这一点我还要继续训练
标签:二分,香蕉,场景,题目,target,piles,int,hours,抽象 From: https://www.cnblogs.com/H-force/p/17742479.html