P3305. 孙悟空吃蟠桃

解题思路

题目本质

注意，本题和 经典题型. 爱吃香蕉的珂珂 完全一致。直接按照课上的写法完成即可。

特殊判断

唯一需要特殊判断的是，当 nums 数组长度大于 h 时，必然无法在 h 小时内吃完所有蟠桃，直接输出 0。

思路展开 本题是「二分答案」的标准形态：不去直接构造答案，而是先猜一个采摘速度 K，再验证这个速度够不够。

• 验证函数 cal_hour_used(nums, k) 计算速度为 k 时摘完所有树的总耗时：每棵树上有 p 个蟠桃，机器人一小时最多摘 k 个且这一小时只守这一棵树，所以这棵树要花 ceil(p / k) 小时，对所有树求和就是总小时数。
• 单调性是二分成立的根基：k 越大，每一项 ceil(p / k) 只会变小或不变，总耗时单调不增。于是「能否在 h 小时内摘完」随 k 增大从不行变为可行，中间存在一个临界速度。
• 二分在左闭右开区间 [1, max(nums)+1) 上找这个临界值：若 cal_hour_used(nums, mid) <= h，说明 mid 已经够快，最小可行速度在左半边，right = mid；否则 mid 太慢，left = mid + 1。退出循环时 left 就是满足条件的最小速度 K。
• 速度上界取 max(nums) 即可：一小时只能处理一棵树，速度再大也快不过「一棵树一小时」。
• 唯一的特判：若树的棵数超过 h（len(nums) > h），即使速度拉满也至少需要每棵树一小时，无法按时摘完，直接输出 0。

复杂度分析 设 n 为蟠桃树棵数（数组 nums 的长度），V 为单棵树上蟠桃数的最大值 max(nums)。cal_hour_used 每次线性扫描全部 n 棵树，为 O(n)；二分迭代 O(log V) 次，每轮调用一次验证函数。总时间复杂度为 O(n log V)，瓶颈在每轮二分的整组求和。除输入外只用常数个变量，额外空间复杂度为 O(1)。