爱吃蟠桃的孙悟空

一、题目描述

孙悟空喜欢吃蟠桃，一天他乘守卫蟠桃园的天兵天将离开了而偷偷的来到王母娘娘的蟠桃园偷吃蟠桃。
已知蟠桃园有 N 棵蟠桃树，第 i 棵蟠桃树上有 N[i]（大于 0）个蟠桃，天兵天将将在 H（不小于蟠桃树棵数）小时后回来。
孙悟空可以决定他吃蟠桃的速度 K（单位：个/小时），每个小时他会选择一颗蟠桃树，从中吃掉 K 个蟠桃，如果这棵树上的蟠桃数小于 K，他将吃掉这棵树上所有蟠桃，然后这一小时内不再吃其余蟠桃树上的蟠桃。
孙悟空喜欢慢慢吃，但仍想在天兵天将回来前将所有蟠桃吃完。
求孙悟空可以在 H 小时内吃掉所有蟠桃的最小速度 K（K 为整数）。

二、输入输出描述

输入描述

• 第一行：若干个正整数，用空格分隔，表示每棵蟠桃树上的蟠桃数量；
• 第二行：一个正整数 H，表示天兵天将返回的时间（小时），且 H ≥ 蟠桃树棵数。

输出描述

• 一个正整数：满足条件的最小进食速度 K；
• 若输入异常（如非数字、蟠桃数≤0、H 小于树的数量等），输出 -1。

三、示例

四、解题思路

1. 核心思想

利用二分查找解决 “最小可行值” 问题：速度K的取值范围是有序的（1 到 maxPeach），且满足 “若速度K可行（总耗时≤H），则所有 > K 的速度都可行；若K不可行，则所有 <K 的速度都不可行” 的单调性，因此可以通过二分查找快速缩小范围，找到最小可行速度，避免暴力枚举（暴力枚举时间复杂度 O (NmaxPeach)，二分查找仅 O (Nlog (maxPeach))，效率大幅提升）。

2. 问题本质分析

该问题是单调性优化问题，属于二分查找的经典应用场景（最小满足条件值）：

• 问题约束：
  • 每小时只能吃一棵树上的蟠桃，每小时最多吃K个；
  • 总耗时≤H，且 H≥树的数量（必要前提）；
• 单调性：速度K越大，总耗时越小；速度K越小，总耗时越大；
• 目标：找到满足 “总耗时≤H” 的最小K。

3. 核心逻辑

• 二分边界确定：
  • 左边界left=1：最小可能速度（每小时吃 1 个）；
  • 右边界right=maxPeach：最大必要速度（再大的速度不会减少总耗时，无意义）；
• 判断条件：对于中间值mid，计算以mid为速度的总耗时：
  • 若总耗时≤H：mid可行，尝试找更小的速度（收缩右边界right=mid）；
  • 若总耗时 > H：mid不可行，需要增大速度（收缩左边界left=mid+1）；
• 循环终止：当left==right时，即为最小可行速度；
• 耗时计算：用整数向上取整公式计算单棵树的耗时，累加得到总耗时，避免浮点运算。

4. 步骤拆解

五、代码实现

import java.util.Scanner;

public class PeachEatingSpeed {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
try {
// 1. 读取并处理第一行（蟠桃数量）
String[] peachStrs = scanner.nextLine().trim().split("\\\\s+");
int[] peaches = new int[peachStrs.length];
int maxPeach = 0;
for (int i = 0; i < peachStrs.length; i++) {
peaches[i] = Integer.parseInt(peachStrs[i]);
// 校验蟠桃数是否大于0
if (peaches[i] <= 0) {
System.out.println(-1);
return;
}
maxPeach = Math.max(maxPeach, peaches[i]);
}

// 2. 读取并处理第二行（时间H）
int H = Integer.parseInt(scanner.nextLine().trim());
// 校验H是否不小于树的数量
if (H < peaches.length) {
System.out.println(-1);
return;
}

// 3. 二分查找最小速度
int left = 1;
int right = maxPeach;
while (left < right) {
int mid = left + (right – left) / 2; // 避免(left+right)溢出
int totalTime = calculateTotalTime(peaches, mid);
if (totalTime <= H) {
// 速度可行，尝试找更小的
right = mid;
} else {
// 速度不够，需要增大
left = mid + 1;
}
}

// 4. 输出最小速度
System.out.println(left);

} catch (Exception e) {
// 输入异常（如非数字、格式错误等）
System.out.println(-1);
} finally {
scanner.close();
}
}

/**
* 计算以指定速度K吃完全部蟠桃的总耗时
* @param peaches 每棵树的蟠桃数量
* @param K 进食速度
* @return 总耗时（小时）
*/
private static int calculateTotalTime(int[] peaches, int K) {
int total = 0;
for (int n : peaches) {
// 向上取整：(n + K – 1) / K 等价于 ceil(n/K)
total += (n + K – 1) / K;
}
return total;
}
}