Leetcode|二分搜索应用|875. 爱吃香蕉的珂珂

SL_World

发布于 2021-09-18 17:34:41

2110

发布于 2021-09-18 17:34:41

文章被收录于专栏：XX

一、暴力穷举

先确定K的范围，然后遍历K从1到maxK，运行超时

二、二分搜索

class Solution {
public:
    int minEatingSpeed(vector<int>& piles, int h) {
        int maxK = -1;
        int minK = -1;
        // 1.获取最大K——最大香蕉数
        for (auto& pile : piles)
            if (pile > maxK) maxK = pile;
        // 2.在[1,maxK]中二分搜索查找最小k
        int left = 1;
        int right = maxK;
        while(left <= right) {
            int mid = left + (right - left) / 2;
            int sum = 0;
            for (int i = 0; i < piles.size(); i++) {
                // 3.向上取整累加
                sum += ceil(piles[i] * 1.0 / mid);
                if (sum > h) {               // minK在右侧
                    left = mid + 1;
                    break;
                }
                if (i == piles.size() - 1) {  // minK在当前或左侧
                    minK = mid;
                    right = mid - 1;
                }
            }
        }
        return minK;
    }
};