明确题目,要求在h小时内吃的最多,用时最长
- 根据题意可以知道:珂珂吃香蕉的速度越小,耗时越多。反之,速度越大,耗时越少,这就抽象成一个函数,x轴是吃香蕉的速度,y轴是吃香蕉的时间,可以知道这是一条随着x增加,y减小的递减函数图像;
- 我们要找的是速度。因为题目限制了珂珂一个小时之内只能选择一堆香蕉吃,因此速度最大值就是这几堆香蕉中,数量最多的那一堆。速度的最小值是1,也就是一小时只吃一根;
- 还是因为珂珂一个小时之内只能选择一堆香蕉吃,因此:每堆香蕉吃完的耗时 = 这堆香蕉的数量 / 珂珂一小时吃香蕉的数量。
函数图像如下,现在题目抽象成,在f(x) = H时,找出x最小一点。利用二分的left_bound方法
class Solution {
public:
//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;
}
int minEatingSpeed(vector<int>& piles, int h)
{
int left = 1, right = 1000000000 + 1;
while (left < right)
{
int mid = left + (right - left) / 2;
if (f(piles, mid) < h)
right = mid;
else if (f(piles, mid) > h)
left = mid + 1;
else if (f(piles, mid) == h)
right = mid;
}
return left;
}
};