leetcode 875. Koko Eating Bananas

本文主要是介绍leetcode 875. Koko Eating Bananas，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意： KoKo（知名大猩猩可可（Koko），出题的作者肯定比较热爱大猩猩）喜欢吃香蕉。

桌子上有好几把香蕉，每一把有piles[i]根香蕉。管理员会离开H 小时，然后KoKo就要在这H小时内偷吃香蕉。

KoKo要在管理员离开的H小时内把所有的香蕉吃完，就得有个吃的速度K。并且KoKo也不想吃的太快。

问题就是求出来这个吃的速度K。保证既能吃完，吃的速度也慢。

大家看完题目一头雾水。

重要的事情说三遍：画图表，画图表，画图表。
bananas/piles 吃的速度K
// 1 2 3 4 5 6 .......
//3 3 2 1 1 1 1
//6 6 3 2 2 2 1
//7 7 4 3 2 2 2
//11 11 6 4 3 3 2
//hours 27 15 10 8 8 7

图画出来了，问题就看出来了一半。

随着K吃的速度变大， hours变小，并且时间还是递减的。

于是乎第一个想法就是二分法就可以用了。那么二分啥那？当然是吃的速度了。通过吃的速度就能计算出一共的时间。然后二分和target Hour比较来缩小查询的集合。

比如start ： 1 end： 11

mid 就是6

通过计算速度为6的时候全部吃完的时间来决定加快吃的速度还是减慢吃的速度。

既然用二分法就要知道K的范围，然后通过K的数值寻找来确定吃香蕉的hours。
1. K的范围。 K是每个小时吃香蕉的速度。最小为1，最大我们可以设置为最大的pile里香蕉数目。该题目为11.
2. 二分法就得有不停的判断来缩小查找的范围
calcHour（mid）和 targetHour 比较。
可以看到随着K的增大， hours越来越小。相当于有序了。
3. 最后退出，要先比较 calcHour（start）再比较calcHour（end）是否为targetHour
我们看这个表格，hours 为8的时候K 为4，5.
题目提到了一句话 Koko likes to eat slowly。
也就是说必须取小的K。

代码如下：

class Solution {
public:
int calcHours(vector<int>& piles, int speed)
{
int ret = 0;

for(int pile:piles)
{
ret += pile/speed;

if(pile % speed !=0)
ret +=1;
}

return ret;
}

int minEatingSpeed(vector<int>& piles, int h) {
//1. 画图画图画图重要的事情说三遍
//bananas K
// 1 2 3 4 5 6
//3 3 2 1 1 1 1
//6 6 3 2 2 2 1
//7 7 4 3 2 2 2
//11 11 6 4 3 3 2
//hours 27 15 10 8 8 7

//图画出来了，问题就看出来了。随着K的数值变大， hours变小。于是乎二分法就可以用了
//既然用二分法就要知道K的范围，然后通过K的数值寻找来确定吃香蕉的hours。
//1. K的范围。 K是每个小时吃香蕉的速度。最小为1，最大我们可以设置为最大的pile里香蕉数目。该题目为11.
//2. 二分法就得有不停的判断来缩小查找的范围
// calcHour（mid）和 targetHour 比较。
// 可以看到随着K的增大， hours越来越小。相当于有序了。
//3. 最后退出，要先比较 calcHour（start）再比较calcHour（end）是否为targetHour
// 我们看这个表格，hours 为8的时候K 为4，5.
// 题目提到了一句话 Koko likes to eat slowly。
// 也就是说必须取小的K。

int start = 1;
int maxBananas = 1;

for(int pile: piles) {
if(pile > maxBananas)
maxBananas = pile;
}

int end = maxBananas;

while(start + 1 < end)
{
int mid = start + (end - start) / 2;
int hours = calcHours(piles, mid);

if(hours > h){
start = mid;
}
else
end = mid;
}

if(calcHours(piles, start) <= h)
return start;

if(calcHours(piles, end) <= h)
return end;
return -1;
}
};