LeetCode 875 Koko Eating Bananas

Tag: 二分搜索 LeetCode Posted on 2022-02-03 09:50:22 Edited on 2022-02-05 16:55:35 Views: 174

题目分析

https://leetcode.com/problems/koko-eating-bananas/

实际上不就是每堆香蕉单独除以吃香蕉速度得到该堆的耗时,之后总耗时要小于 h,据此我们可以算出给定 k 其是否 okay。

这是一个二分搜索题目,k 的最小值为 1,最大值为列表中的最大值,因为再大也没用意义了。

迭代法

class Solution {
public:
    int minEatingSpeed(vector<int>& piles, int h) {
        int l = 1;
        int r = *max_element(piles.begin(), piles.end());
        while (l <= r) {
            int m = l + (r - l) / 2;
            if (isOkay(piles, h, m)) {
                r = m - 1;
            } else {
                l = m + 1;
            }
        }
        return l;
    }
    
    bool isOkay(vector<int>& piles, int h, int k) {
        int count = 0;
        for (int i = 0; i < piles.size(); i++) {
            count += piles[i] / k + int(piles[i] % k != 0);
        }
        return count <= h;
    }
};

未经允许,禁止转载,本文源站链接:https://iamazing.cn/