【中等】爱吃香蕉的珂珂(抽象二分问题)

【中等】爱吃香蕉的珂珂(抽象二分问题)
【中等】爱吃香蕉的珂珂(抽象二分问题)
明确题目,要求在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;
    }
};
上一篇:877. 石子游戏


下一篇:leetcode 1962. 移除石子使总数最小