875. 爱吃香蕉的珂珂

题目链接：875. 爱吃香蕉的珂珂

题目描述

珂珂喜欢吃香蕉。这里有 n 堆香蕉，第 i 堆中有 piles[i] 根香蕉。警卫已经离开了，将在 h 小时后回来。

珂珂可以决定她吃香蕉的速度 k （单位：根/小时）。每个小时，她将会选择一堆香蕉，从中吃掉 k 根。如果这堆香蕉少于 k 根，她将吃掉这堆的所有香蕉，然后这一小时内不会再吃更多的香蕉。

珂珂喜欢慢慢吃，但仍然想在警卫回来前吃掉所有的香蕉。返回她可以在 h 小时内吃掉所有香蕉的最小速度 k（k 为整数）。

核心思考：对值域进行二分查找

这道题是典型的“二分答案”问题。由于吃香蕉的速度 $k$ 和吃完所有香蕉所需的总时间 $Time(k)$ 存在明确的单调递减关系（速度越快，耗时越短），因此可以通过二分查找来寻找满足 $Time(k) \le h$ 的最小整数速度。

1. 基础实现（求左侧边界）

在初步实现中，我们将速度的下限设为 1，上限设为一个固定的大常数（如 1000000000）。通过二分查找不断调整速度：

• 如果当前速度计算出的耗时大于 $h$，说明太慢了，需要增加速度，此时 left_speed = mid + 1。
• 如果耗时小于等于 $h$，说明速度够用，但可能还能再慢一点，此时向左收缩边界 right_speed = mid - 1。

最终找到的 left_speed 就是满足条件的最小速度。

class Solution:
    def minEatingSpeed(self, piles: List[int], h: int) -> int:
        def time_cost(piles,speed):
            # 这个函数应该设计用来计算以这个效率吃所需要消耗的总时间
            times = 0
            for x in piles:
                if x % speed == 0:
                    times += (x//speed)
                else:
                    times += (x//speed + 1)
            return times

        left_speed = 1
        right_speed = 1000000000
        
        # 二分查找最靠左侧的效率
        while left_speed <= right_speed:
            mid = left_speed + (right_speed - left_speed) // 2
            if time_cost(piles,mid) > h:
                # 时间消耗比h多了，说明超时了，要加快效率
                left_speed = mid + 1
            elif time_cost(piles,mid) < h:
                right_speed = mid - 1
            elif time_cost(piles,mid) == h:
                right_speed = mid - 1
            
        return left_speed

基于上述思路的代码虽然可以求解，但存在几个明显的性能瓶颈，导致运行时间不理想。

2. 代码优化

为了提高执行效率，我们需要关注以下三个改进点：

1. 缩小初始右边界：因为一小时最多只能吃一堆香蕉，所以最大有意义的速度其实就是数组中最大那一堆的数量 max(piles)。将上限设为这个值可以减少无意义的二分轮数。
2. 避免重复计算：在原来的 while 循环分支中，最多会调用 3 次 time_cost 函数。由于这是一个 $O(N)$ 复杂度的函数，重复调用开销极大。应该将结果先计算并缓存到变量 current_cost 中。
3. 优化向上取整运算：原逻辑中的 if-else 分支可以通过公式 (x + speed - 1) // speed 来实现向上取整。结合 Python 的生成器表达式和内置的 sum 函数，执行速度会更快。

优化后的代码如下：

class Solution:
    def minEatingSpeed(self, piles: List[int], h: int) -> int:
        def time_cost(piles, speed):
            # 使用生成器表达式和向上取整技巧，推给底层的 C 实现来加速 sum
            return sum((x + speed - 1) // speed for x in piles)

        left_speed = 1
        right_speed = max(piles) # 缩小初始右边界

        while left_speed <= right_speed:
            mid = left_speed + (right_speed - left_speed) // 2
            
            # 将耗时缓存，避免多次 O(N) 调用
            current_cost = time_cost(piles, mid)
            
            if current_cost > h:
                left_speed = mid + 1
            else:
                # current_cost <= h，说明速度够用，尝试寻找更小的左边界
                right_speed = mid - 1

        return left_speed

优化后的性能表现：

复杂度分析

• 时间复杂度：$O(N \log M)$，其中 $N$ 是数组 piles 的长度，$M$ 是数组中的最大元素。确定初始右边界需要 $O(N)$ 时间。搜索区间的大小为 $M$，因此需要进行 $O(\log M)$ 次二分。每次二分需要调用 time_cost 遍历一次数组，耗时 $O(N)$。总时间复杂度为两者相乘。
• 空间复杂度：$O(1)$。算法只使用了常数级别的额外空间来记录速度和时间等变量。

ACM 模式

本节提供 ACM 竞赛风格的完整可运行代码，包含输入输出处理。

输入格式：

num1 num2 num3 ... numN
k

第一行输入数组，第二行输入整数 k。

完整代码：

import sys

class Solution:
    def minEatingSpeed(self, piles: List[int], h: int) -> int:
    def time_cost(piles,speed):
                # 这个函数应该设计用来计算以这个效率吃所需要消耗的总时间
                times = 0
                for x in piles:
                    if x % speed == 0:
                        times += (x//speed)
                    else:
                        times += (x//speed + 1)
                return times

            left_speed = 1
            right_speed = 1000000000

            # 二分查找最靠左侧的效率
            while left_speed <= right_speed:
                mid = left_speed + (right_speed - left_speed) // 2
                if time_cost(piles,mid) > h:
                    # 时间消耗比h多了，说明超时了，要加快效率
                    left_speed = mid + 1
                elif time_cost(piles,mid) < h:
                    right_speed = mid - 1
                elif time_cost(piles,mid) == h:
                    right_speed = mid - 1

            return left_speed

def main():
    data = sys.stdin.read().strip().split()
    k = int(data[-1])
    nums = list(map(int, data[:-1]))

    sol = Solution()
    result = sol.minEatingSpeed(nums, k)
    print(result)

if __name__ == "__main__":
    main()

运行示例：

echo -e "1 3 -1 -3 6 7\n3" | python solution.py