Koko 吃香蕉

Koko Eating Bananas

专题: Algorithmic Programming / 算法编程
难度: L4
来源: QuantQuestion

题目详情

给定整数数组 piles，其中 piles[i] 是第 i 堆香蕉数量；再给定整数 h 表示总共可用的小时数。

你需要选一个每小时吃香蕉速度 k。每小时只能选择一堆吃 k 根；若该堆不足 k 则吃完该堆但不能在同一小时换堆。

返回最小整数 k，使得你能在 h 小时内吃完所有香蕉。

You are given an integer array piles where piles[i] is the number of bananas in the ith pile. You are also given an integer h, which represents the number of hours you have to eat all the bananas.

You may decide your bananas-per-hour eating rate of k. Each hour, you may choose a pile of bananas and eats k bananas from that pile. If the pile has less than k bananas, you may finish eating the pile but you can not eat from another pile in the same hour.

Return the minimum integer k such that you can eat all the bananas within h hours.

Example 1:

Input: piles = [1,4,3,2], h = 9

Output: 2 Explanation: With an eating rate of 2, you can eat the bananas in 6 hours. With an eating rate of 1, you would need 10 hours to eat all the bananas (which exceeds h=9), thus the minimum eating rate is 2.

Example 2:

Input: piles = [25,10,23,4], h = 4

Output: 25 Constraints:

1 <= piles.length <= 1,000 piles.length <= h <= 1,000,000 1 <= piles[i] <= 1,000,000,000

解析

对 k 在 $[1,\max(piles)]$ 上二分。

检查函数：给定 k，计算 $\sum_i \lceil piles[i]/k\rceil$ ，若不超过 h 则 k 可行。

用二分寻找最小可行 k。

Original Explanation


class Solution:
    def minEatingSpeed(self, piles: List[int], h: int) -> int:
        l, r = 1, max(piles)
        res = r

        while l <= r:
            k = (l + r) // 2

            totalTime = 0
            for p in piles:
                totalTime += math.ceil(float(p) / k)
            if totalTime <= h:
                res = k
                r = k - 1
            else:
                l = k + 1
        return res