Mind palace

some thoughts

0%

875. Koko Eating Bananas

Posted on Edited on In Disqus:
Symbols count in article: 882 Reading time ≈ 1 mins.

二分猜数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int minEatingSpeed(vector<int>& piles, int H) {
        int lo = 1, hi = 1e9;
        while (lo < hi) {
            int m = lo + (hi - lo) / 2;
            if (isValid(piles, H, m)) {
                hi = m;
            } else {
                lo = m + 1;
            }
        }
        return lo;
    }

    bool isValid(const vector<int> &piles, int H, int m) {
        return accumulate(begin(piles), end(piles), 0, [m](int x, int y) { return x + (y - 1) / m + 1; }) <= H;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int minEatingSpeed(vector<int>& piles, int H) {
        int lo = 1, hi = *max_element(begin(piles), end(piles));
        while (lo < hi) {
            int m = lo + (hi - lo) / 2;
            if (isValid(piles, H, m)) {
                hi = m;
            } else {
                lo = m + 1;
            }
        }
        return lo;
    }

    bool isValid(const vector<int> &piles, int H, int m) {
        return accumulate(begin(piles), end(piles), 0, [m](int x, int y) { return x + ceil(y / (double)m); }) <= H;
    }
};