1231.Divide_Chocolate.md

1231. Divide Chocolate

• Google

• Binary Search, Greedy

• Hints:

  • After dividing the array into K+1 sub-arrays, you will pick the sub-array with the minimum sum.
  • Divide the sub-array into K+1 sub-arrays such that the minimum sub-array sum is as maximum as possible.
  • Use the binary search with greedy check.

• Similar Questions:

  • 1231.Divide Chocolate
  • 875.Koko Eating Bananas
  • 774.Minimize Max Distance to Gas Station
  • 410.Split Array Largest Sum

• The question is to find the maximum sum of subarray and this subarray should be the subarray with minimum sum.
  So the basic condition is the sum of this subarray is minimum. After satisfied this basic condition, we can find the maximum sum.
  [将整个 array 分割成 K+1 个 subarray 后，然后选择 sum 最小的 array，这个 sum 要是所有可能中最大的。]
  If if(condition), the sum may be my ans or too smaller (can be larger). That means if(condition) left = mid;.

Method 1.

Ref

class Solution {
    public int maximizeSweetness(int[] sweetness, int K) {
        int left = 1;   // The possible minimum value
        int right = (int)1e9 / (K + 1); // The possible Maximum minimum number
        while(left < right) {
            int mid = (left + right + 1) / 2;
            int cur = 0;    // sum of curr sub-array
            int cuts = 0;   // # of cut
            for(int a: sweetness) {
                if((cur += a) >= mid) {
                    cur = 0;
                    if(++cuts > K) {
                        break;
                    }
                }
            }
            if(cuts > K) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }
}