个人网站实例,固原建设厅官方网站,技术支持 昆明网站建设,网页设计师职业资格证书题目描述
珂珂喜欢吃香蕉。这里有 n 堆香蕉#xff0c;第 i 堆中有 piles[i] 根香蕉。警卫已经离开了#xff0c;将在 h 小时后回来。
珂珂可以决定她吃香蕉的速度 k #xff08;单位#xff1a;根/小时#xff09;。每个小时#xff0c;她将会选择一堆香蕉#xff0c…题目描述
珂珂喜欢吃香蕉。这里有 n 堆香蕉第 i 堆中有 piles[i] 根香蕉。警卫已经离开了将在 h 小时后回来。
珂珂可以决定她吃香蕉的速度 k 单位根/小时。每个小时她将会选择一堆香蕉从中吃掉 k 根。如果这堆香蕉少于 k 根她将吃掉这堆的所有香蕉然后这一小时内不会再吃更多的香蕉。
珂珂喜欢慢慢吃但仍然想在警卫回来前吃掉所有的香蕉。
返回她可以在 h 小时内吃掉所有香蕉的最小速度 kk 为整数。
示例 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 piles.length 104piles.length h 1091 piles[i] 109
解答
class Solution {
public:int minEatingSpeed(vectorint piles, int h) {// 二分查找去尝试能够吃完香蕉的最小速度// 由题意知吃香蕉速度越小耗时越多反之速度越大耗时越小即单调性// 吃每堆香蕉的耗时 这堆香蕉的数量 / 一小时吃香蕉的数量不能整除要向上取整int maxVal 1;for(int num : piles){maxVal max(maxVal, num); // 求香蕉数量最多的堆}// 速度最小的时候耗时最长// 速度最大的时候就是最大堆香蕉的数量保证每堆都在1h内吃完int left 1, right maxVal;while(left right){int mid left (right - left) / 2;if(calculateSum(piles, mid) h) // 速度太慢则把左边界右移{left mid 1;}else // 速度太快则把右边界左移{right mid;}}return left; // 最后能到一个刚刚好的速度}
private:// 计算以 speed 的速度要吃的时间int calculateSum(vectorint piles, int speed){int sum 0;for(int num : piles){sum (num % speed 0 ? num / speed : num / speed 1);}return sum;}
};
