1052-狒狒吃香蕉

题目如下

狒狒喜欢吃香蕉。这里有 N 堆香蕉，第 i 堆中有 piles[i] 根香蕉。警卫已经离开了，将在 H 小时后回来。

狒狒可以决定她吃香蕉的速度 K （单位：根/小时）。每个小时，她将会选择一堆香蕉，从中吃掉 K 根。如果这堆香蕉少于 K 根，她将吃掉这堆的所有香蕉，然后这一小时内不会再吃更多的香蕉，下一个小时才会开始吃另一堆的香蕉。

狒狒喜欢慢慢吃，但仍然想在警卫回来前吃掉所有的香蕉。

返回她可以在 H 小时内吃掉所有香蕉的最小速度 K（K 为整数）。

示例 1：
输入: piles = [3,6,7,11], H = 8
输出: 4

示例 2：
输入: piles = [30,11,23,4,20], H = 5
输出: 30

示例 3：
输入: piles = [30,11,23,4,20], H = 6
输出: 23

解题思路

二分查找
虽然目前不清楚狒狒吃香蕉的速度，但是可以得知狒狒的速度肯定需要大于等于 1，同时也要小于等于最大的一堆香蕉数量 max，因为若大于 max 每小时也只能吃一堆，所以更大的速度是没有意义的。这时候可以得到狒狒吃香蕉的速度应该在 [1, max]，可以使用二分查找算法确定速度。取 1 和 max 的中间值 mid，计算出速度为 mid 时吃完香蕉所需时间 t。

如果时间 t 大于时间 H，则说明狒狒吃的太慢了，需要在 [mid + 1, max] 中搜索速度。
如果时间 t 小于等于时间 H，则还需要判断 mid - 1 的速度吃完香蕉的时间 t2。如果 t2 大于 H，那么说明 mid 为最慢吃完香蕉所需时间（同时需要说明 若 mid 为 1，则无需判断 mid - 1 的情况，直接确定 1 为最慢吃完香蕉所需时间）。如果 t2 小于 H，则说明当前的速度太快，需要在 [1, mid - 1] 中搜索速度。
整个过程其实就是在 1 根到 max 根之间做二分查找。如果香蕉的堆数为 m，最大的堆数的香蕉数量为 n，那么算法的时间复杂度为 O(mlogn)。

说明一下 countTime 函数计算狒狒当前速度吃香蕉的时间，因为题目中说 “如果这堆香蕉少于 K 根，她将吃掉这堆的所有香蕉，然后这一小时内不会再吃更多的香蕉，下一个小时才会开始吃另一堆的香蕉” ，那么狒狒无论选择何种策略吃香蕉，其吃完所有香蕉的时间都与吃香蕉堆的选择顺序无关。

解题代码

class Solution
{
private://返回狒狒速度 k 时需要吃完香蕉的时间int countTime(vector<int>& piles, int k){int t = 0;for (auto& p : piles){//t += (p - 1) / k + 1;t += p / k;t += ((p % k) > 0);}return t;}public:int minEatingSpeed(vector<int>& piles, int h) {int left = 1;int right = *max_element(piles.begin(), piles.end());while (left <= right) {int mid = left + ((right - left) >> 1);if (countTime(piles, mid) <= h) {if (mid == 1 || countTime(piles, mid - 1) > h) {return mid;}right = mid - 1;}else {left = mid + 1;}}return -1;}
};

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