题目描述
孙悟空来到了蟠桃园偷吃蟠桃。蟠桃园有N棵桃树，每棵树上都有一定数量的蟠桃。守卫将在H小时后回来。孙悟空每小时可以选择吃一棵树上的所有蟠桃（如果数量少于他选择的速度，则全部吃掉），并且在这一个小时内不会吃其他树上的桃子。孙悟空希望以尽可能慢的速度吃蟠桃，但又要确保在守卫回来之前吃完所有的桃子。题目要求计算孙悟空能在H小时内吃完所有桃子的最小速度K（个/小时），如果以任何速度都吃不完，则返回0。
输入描述
- 第一行输入为N个数字，表示桃树的数量，接下来是N个数字，用空格分隔，表示每棵桃树上蟠桃的数量。
- 第二行输入为一个数字H，表示守卫离开的时间（小时）。
输出描述
- 输出一个整数，表示孙悟空能在H小时内吃完所有桃子的最小速度K。如果以任何速度都吃不完，则输出0。
解题思路
这个问题可以通过二分查找算法来解决。因为速度K与吃完所有桃子所需的时间成反比，即速度越快，所需时间越少，这是一个单调关系。因此，可以通过二分查找找到满足条件的最小速度。
- 确定二分查找的初始范围：最小速度可以设为1（即每小时至少吃一个桃子），最大速度可以设为桃树上最多蟠桃的数量。
- 二分查找过程：
- 在当前的速度范围内，选择一个中间速度mid。
- 计算以这个速度吃完所有桃子所需的时间。
- 如果所需时间小于等于H，说明这个速度或者更小的速度可能在H小时内吃完所有桃子，因此将搜索范围缩小到左半部分（即更小的速度）。
- 如果所需时间大于H，说明这个速度无法在H小时内吃完所有桃子，因此需要尝试更大的速度，将搜索范围扩大到右半部分。
- 结束条件：当搜索范围收敛到一个单独的速度时，该速度即为所求的最小速度K。
示例
输入样例1：
2 3 4 5 4 5
5
输出样例1：
5
对于样例1，孙悟空以每小时吃5个蟠桃的速度，可以在5小时内吃完所有蟠桃，这是最小的可行速度。
输入样例2：
2 3 4 5 3
输出样例2：
0
对于样例2，即使孙悟空以最快速度吃桃，也无法在3小时内吃完所有蟠桃，因此输出0。
输入样例3：
30 11 23 4 20 6
6
输出样例3：
23
对于样例3，孙悟空需要以每小时至少吃23个蟠桃的速度，才能在6小时内吃完所有蟠桃。
代码实现
以java为例，代码实现可以参考以下形式：
import java.util.Scanner;
public class MonkeyEatingPeaches {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
// 读取桃树数量
int N = scanner.nextInt();
// 读取每颗桃树上蟠桃的数量
int[] peaches = new int[N];
for (int i = 0; i < N; i++) {
peaches[i] = scanner.nextInt();
}
// 读取守卫离开的时间（小时）
int H = scanner.nextInt();
// 调用函数计算最小速度
int minSpeed = findMinEatingSpeed(peaches, H);
// 如果存在解决方案，则输出最小速度；否则输出0（理论上不会发生，因为每颗树上都有蟠桃）
if (minSpeed > 0) {
System.out.println(minSpeed);
} else {
// 在这个特定问题中，由于每颗树上都有蟠桃，且H > 0，因此实际上不会输出0
// 但为了代码的健壮性，还是保留了这个判断
System.out.println("No solution possible (theoretically should not happen),0");
}
scanner.close();
}
/**
* 寻找最小的吃蟠桃速度
*
* @param peaches 整数数组，表示每棵树上的蟠桃数量
* @param H 整数，表示小时数
* @return 返回整数，表示最小的吃蟠桃速度
*/
private static int findMinEatingSpeed(int[] peaches, int H) {
// 最小速度为1（因为速度不能为0）
int left = 1;
// 最大速度初始化为0，稍后在循环中更新
int right = 0;
// 遍历所有桃树，确定可能的最大速度
for (int peach : peaches) {
// 更新最大速度，确保它至少为树上最多的蟠桃数
right = Math.max(right, peach);
}
// 二分查找合适的吃蟠桃速度
while (left < right) {
// 计算中间速度
int mid = left + (right - left) / 2;
// 检查以mid速度是否能在H小时内吃完所有蟠桃
if (canEatAllInHours(peaches, mid, H)) {
// 如果可以，尝试更小的速度
right = mid;
} else {
// 如果不可以，需要更大的速度
left = mid + 1;
}
}
// 当left == right时，循环结束，left即为所求的最小速度
return left;
}
/**
* 判断在有限时间内以给定速度是否能吃完所有桃子
*
* @param peaches 桃子数量数组
* @param speed 吃桃子的速度
* @param H 可用的总时间（小时）
* @return 如果在规定时间内可以吃完所有桃子，则返回true；否则返回false
*/
private static boolean canEatAllInHours(int[] peaches, int speed, int H) {
// 总时间变量初始化为0
int totalHours = 0;
// 遍历桃子数组，计算吃每个桃子所需的时间，并累加到总时间中
for (int peach : peaches) {
// 计算吃掉当前桃子所需的时间，使用向上取整的方法确保精度
totalHours += (peach + speed - 1) / speed;
}
// 返回判断结果：如果总时间小于或等于可用时间H，则返回true，表示可以吃完；否则返回false
return totalHours <= H;
}
}
运行解析
输入：
4
2 3 4 5
4
输出：
5
对于输入4(代表四棵桃树) 2 3 4 5（每棵分别有2、3、4、5个蟠桃）和 4（代表守卫离开的时间为4小时），我们需要计算孙悟空能在4小时内吃完所有蟠桃的最小速度。
让我们来分析一下：
- 如果速度为1，那么吃完所有蟠桃需要的时间将远远超过4小时。
- 如果速度为2，时间仍然是太长，因为至少需要
2+2+2+3=9个时间单位（但每个时间单位只能吃一个，所以实际上需要向上取整）。 - 如果速度为3，时间仍然不够，因为至少需要
1+1+2+2=6个时间单位。 - 如果速度为4，时间还是不够，因为需要
1+1+1+2=5个时间单位（但第四棵树上的5个蟠桃需要2个时间单位）。 - 如果速度为5，孙悟空可以在4小时内吃完所有蟠桃：第一棵树需要1小时，第二棵树需要1小时，第三棵树需要1小时，第四棵树需要1小时，总共4小时。
然而，这里有一个重要的点需要注意：在计算所需时间时，我们应该使用“向上取整”的方法，因为孙悟空不能分割蟠桃。例如，如果一棵树上有5个蟠桃，而孙悟空的速度是5，那么他需要1个小时来吃完这些蟠桃（而不是0.5小时或类似的时间）。
基于上述分析，对于输入 2 3 4 5 和 4，输出确实应该是 5，因为这是孙悟空能在4小时内吃完所有蟠桃的最小速度。
但是，请注意，如果findMinEatingSpeed方法中的canEatAllInHours函数没有正确实现“向上取整”的逻辑，那么它可能会给出错误的结果。在给出的代码示例中，canEatAllInHours函数已经使用了(peach + speed - 1) / speed来实现向上取整（这是整数除法在Java中的行为，当除不尽时自动向下取整，但通过加speed-1实现了向上取整的效果）。因此，如果输入是2 3 4 5和4，且使用上述代码，输出应该是5。