1231.md

1231 分享巧克力

Solution 1

通过二分对可能的结果集进行搜索, 需要确定结果集的上界和下届.

class Solution {
    public int maximizeSweetness(int[] sweetness, int k) {
        int minResult = sweetness[0], maxResult = 0;

        for (int item : sweetness) {
            minResult = Math.min(minResult, item);
            maxResult = maxResult + item;
        }

        while (minResult < maxResult) {
            int target = (minResult + maxResult + 1) / 2;
            if (canGetSweetness(sweetness, k, target)) {
                minResult = target;
            } else {
                maxResult = target - 1;
            }
        }

        return minResult;
    }

    private boolean canGetSweetness(int[] sweetness, int k, int target) {
        int sum = 0;
        int count = 0;

        // 切分是连续的.
        for (int item : sweetness) {
            sum += item;
            if (sum >= target) {
                sum = 0;
                count++;
            }
        }

        return count >= k + 1;
    }
}