力扣1231 经典二分 最大化最小值 或者 最小化最大值

https://leetcode-cn.com/problems/divide-chocolate/

class Solution {
public:
    int check(vector<int>& sweetness, int minSize) {
        //判断当最小快为minSize时，最多能分成多少块
        int cur = 0;
        int ret = 0;
        for (int i : sweetness) {
            cur += i;
            if (cur >= minSize) {
                ++ret;
                cur = 0;
            }
        }
        return ret;
    }

    int maximizeSweetness(vector<int>& sweetness, int K) {
        int sum = 0;
        for (int i : sweetness) {
            sum += i;
        }

        if (K == 0) {
            return sum;
        }

        int left = 1, right = sum / K;
        //使用二分查询最小值
        //贪心思想，在块符合>=mid时，尽量把块分的最小

        while (left < right) {
            int mid = (left + right + 1) / 2;
            if (check(sweetness, mid) >= K + 1) {
                left = mid;
            }
            else {
                right = mid - 1;
            }
        }

        return right;
    }
};