华为OD机试_2025 B卷_爱吃蟠桃的孙悟空（Python，100分）（附详细解题思路）
题目描述
孙悟空爱吃蟠桃，有一天趁着蟠桃园守卫不在来偷吃。已知蟠桃园有 N 棵桃树，每颗树上都有桃子，守卫将在 H 小时后回来。
孙悟空可以决定他吃蟠桃的速度K（个/小时），每个小时选一颗桃树，并从树上吃掉 K 个，如果树上的桃子少于 K 个，则全部吃掉，并且这一小时剩余的时间里不再吃桃。
孙悟空喜欢慢慢吃，但又想在守卫回来前吃完桃子。
请返回孙悟空可以在 H 小时内吃掉所有桃子的最小速度 K（K为整数）。如果以任何速度都吃不完所有桃子，则返回0。
输入描述
第一行输入为 N 个数字，N 表示桃树的数量，这 N 个数字表示每颗桃树上蟠桃的数量。
第二行输入为一个数字，表示守卫离开的时间 H。
其中数字通过空格分割，N、H为正整数，每颗树上都有蟠桃，且 0 < N < 10000，0 < H < 10000。
输出描述
吃掉所有蟠桃的最小速度 K，无解或输入异常时输出 0。
用例
| 输入 | 2 3 4 5 4 |
| 输出 | 5 |
| 说明 | 无 |
| 输入 | 2 3 4 5 3 |
| 输出 | 0 |
| 说明 | 无 |
| 输入 | 30 11 23 4 20 6 |
| 输出 | 23 |
| 说明 | 无 |
孙悟空吃蟠桃问题的最优解：二分查找的应用
核心解题思路
题目要求找到孙悟空能在H小时内吃完所有蟠桃的最小速度K（整数）。这里的难点在于，如何高效地找到满足条件的最小K值。经过分析，可以发现这个问题非常适合使用二分查找来解决。
关键观察点：
- 范围确定：速度K的最小值为1，最大值为桃树中最多桃子数max_pile（当K≥max_pile时，每棵树最多1小时）。
- 时间计算：对于给定K，总时间=所有桃树的桃子数除以K向上取整之和。
- 单调性：当K增大时，总时间减少。因此可以使用二分法快速缩小范围。
- 边界条件：
- 若H < 桃树数量N，直接返回0（每棵树至少需要1小时）。
- 最小可能的K值应满足总桃子数sum除以H的向上取整（确保每小时吃够量）。
解题步骤详解
1. 输入处理与边界检查
首先读取输入并验证有效性。若输入异常或H < N，直接返回0。
2. 确定搜索范围
- 左边界left：最大值为sum(piles)/H的向上取整，保证每小时吃够总量。
- 右边界right：桃树中最大桃子数max_pile。
3. 二分查找最小K值
遍历可能的K值，计算每个K对应的总时间：
- 若总时间≤H，尝试更小K（调整右边界）。
- 若总时间>H，必须增大K（调整左边界）。
4. 验证并返回结果
最终检查找到的K是否有效，若无解则返回0。
代码实现
import mathdef main():try:# 读取输入piles = list(map(int, input().split()))H = int(input())# 输入验证if H <= 0 or len(piles) == 0 or any(p <= 0 for p in piles):print(0)returnn = len(piles)if H < n:print(0)returntotal = sum(piles)max_pile = max(piles)# 计算左边界left = math.ceil(total / H)right = max_pileif left > right:print(0)returnmin_k = None # 记录符合条件的K# 二分查找while left <= right:mid = (left + right) // 2time = 0for p in piles:time += math.ceil(p / mid)if time > H:breakif time <= H:# 当前mid可行，尝试更小的Kmin_k = midright = mid - 1else:# 需要增大Kleft = mid + 1if min_k is not None:print(min_k)else:print(0)except:print(0)if __name__ == "__main__":main()
案例分析
示例1：
输入：2 3 4 5 和 H=4
- 总和sum=14，ceil(14/4)=4，max_pile=5 → left=4, right=5。
- 二分找到K=5时总时间为4小时，符合条件。
示例3：
输入：30 11 23 4 20 和 H=6
- ceil(88/6)=15，max_pile=30 → 搜索范围15~30。
- 二分找到K=23时总时间6小时，符合条件。
总结
通过二分法快速缩小搜索范围，结合合理的边界条件确定，能够高效解决此类速度最优化问题。该算法的时间复杂度为O(N log max_pile)，适用于题目给定的数据范围。