如何用java二分法解决某动物园的猩猩“小黑子”很喜欢吃香蕉,但是香蕉有警卫看守,“小黑子”不能吃到香蕉会很伤心,当警卫离开时它可以偷偷吃到香蕉。这里有 n 堆香蕉,每一堆的香蕉数量不详。此时警卫已经离开了,将在 h 小时后回来。“小黑子”可以决定自己吃香蕉的速度 k (单位:根/小时)。每过一个小时,它将会另选一堆香蕉,并从中吃掉 k 根。如果这堆香蕉少于 k 根,它将吃掉这堆的所有香蕉,然后这一小时内不会再吃更多的香蕉。 “小黑子”喜欢细嚼慢咽,但仍然想在警卫回来前吃掉所有的香蕉。返回它可以在 h 小时内吃掉所有香蕉的最小速度 k(k 为整数),如果吃不完则输出“不可能吃完”。
时间: 2023-02-05 18:08:28 浏览: 179
在这道题中,我们可以使用二分法来解决。
首先,定义一个方法来判断是否能在 h 小时内吃掉所有的香蕉。我们将二分法的中间值设为 k,然后遍历每一堆香蕉,计算出需要的时间。如果总时间大于 h,则说明 k 值太小,我们需要增大 k 的值。反之,如果总时间小于等于 h,则说明 k 值可以满足条件,我们需要减小 k 的值。
代码如下:
```
public int minEatingSpeed(int[] piles, int h) {
int left = 1;
int right = 0;
for (int pile : piles) {
right = Math.max(right, pile);
}
while (left < right) {
int mid = left + (right - left) / 2;
int time = 0;
for (int pile : piles) {
time += (pile + mid - 1) / mid;
}
if (time > h) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}
```
在上面的代码中,我们首先将二分法的左端点设为 1,右端点设为最大的香蕉数。然后我们在 while 循环中使用二分法的常规操作,计算出中间值 mid,并遍历每一堆香蕉,计算出需要的时间。如果总时间大于 h,则说明 k 值太小,我们需要增大 k 的值。反之,如果总时间小于等于 h,则说明 k 值可以满足条件,我们
阅读全文