LeetCode 875. Koko Eating Bananas

2023.3.8 Daily Challenge
難度：Medium

問題

給 n 堆香蕉，每堆有 piles[n] 根。

目標是選一個盡量小吃速 k （每小時吃 k 根），然後希望在 h 小時內吃完。

Koko 每次可以挑一堆吃，挑了那堆一定會吃完，然後吃完時間有剩也會等到這小時結束再換下一堆。舉例來說，假設這堆有 7 根，吃速 k = 2 ，總共要吃 7 / 2 = 3.5 小時，而剩下 0.5 小時他會坐在那啥都不幹，這小時結束才會換下一堆。

解法

• piles.length 最大 10^4 ，給定 k 算一次所花費時間 h 的時間複雜度 O(n) ，應該還不錯快。
• piles.length <= h ，所以你只要一小時吃一堆（ k = max_element(piles) ），h 內一定吃得完。
• k 越小 h 越大。
• piles[i] < 10^9 ，ln(10^9) = 20

所以這邊直接在 [1, max_element(piles)] 內二分搜到最小的 k 就行。

坑

本來從 k = 0 開始找就 divide by zero 炸了，小雷注意。

Code

class Solution
{
public:
    int minEatingSpeed(vector<int> &piles, int h)
    {
        auto getH = [&](int &k)
        {
            int h = 0;
            for (auto pile : piles)
            {
                auto z = pile / k;
                h += ceil(static_cast<double>(pile) / k);
            }
            return h;
        };

        function<int(int, int)> findK = [&](int l, int r) -> int
        {
            if (l >= r)
                return l;

            auto m = (l + r) / 2;
            auto hx = getH(m);
            if (hx > h)
                return findK(m + 1, r);
            else
                return findK(l, m);
        };

        auto max = *max_element(piles.begin(), piles.end());

        return findK(1, max);
    }
};

Tags

• LeetCode