Question

1231. Divide Chocolate

中文文档

Description

You have one chocolate bar that consists of some chunks. Each chunk has its own sweetness given by the array sweetness.

You want to share the chocolate with your k friends so you start cutting the chocolate bar into k + 1 pieces using k cuts, each piece consists of some consecutive chunks.

Being generous, you will eat the piece with the minimum total sweetness and give the other pieces to your friends.

Find the maximum total sweetness of the piece you can get by cutting the chocolate bar optimally.

 

Example 1:

Input: sweetness = [1,2,3,4,5,6,7,8,9], k = 5
Output: 6
Explanation: You can divide the chocolate to [1,2,3], [4,5], [6], [7], [8], [9]

Example 2:

Input: sweetness = [5,6,7,8,9,1,2,3,4], k = 8
Output: 1
Explanation: There is only one way to cut the bar into 9 pieces.

Example 3:

Input: sweetness = [1,2,2,1,2,2,1,2,2], k = 2
Output: 5
Explanation: You can divide the chocolate to [1,2,2], [1,2,2], [1,2,2]

 

Constraints:

• 0 <= k < sweetness.length <= 104
• 1 <= sweetness[i] <= 105

Solutions

Solution 1: Binary Search + Greedy

We notice that if we can eat a piece of chocolate with sweetness $x$, then we can also eat all chocolates with sweetness less than or equal to $x$. This shows monotonicity, therefore, we can use binary search to find the maximum $x$ that satisfies the condition.

We define the left boundary of the binary search as $l=0$, and the right boundary as $r=\sum_{i=0}^{n-1} sweetness[i]$. Each time, we take the middle value $mid$ of $l$ and $r$, and then determine whether we can eat a piece of chocolate with sweetness $mid$. If we can, then we try to eat a piece of chocolate with greater sweetness, i.e., let $l=mid$; otherwise, we try to eat a piece of chocolate with smaller sweetness, i.e., let $r=mid-1$. After the binary search ends, we return $l$.

The key to the problem is how to determine whether we can eat a piece of chocolate with sweetness $x$. We can use a greedy approach, traverse the array from left to right, accumulate the current sweetness each time, when the accumulated sweetness is greater than or equal to $x$, the chocolate count $cnt$ is increased by $1$, and the accumulated sweetness is reset to zero. Finally, check whether $cnt$ is greater than $k$.

The time complexity is $O(n \times \log \sum_{i=0}^{n-1} sweetness[i])$, and the space complexity is $O(1)$. Where $n$ is the length of the array.

class Solution:
  def maximizeSweetness(self, sweetness: List[int], k: int) -> int:
    def check(x: int) -> bool:
      s = cnt = 0
      for v in sweetness:
        s += v
        if s >= x:
          s = 0
          cnt += 1
      return cnt > k

    l, r = 0, sum(sweetness)
    while l < r:
      mid = (l + r + 1) >> 1
      if check(mid):
        l = mid
      else:
        r = mid - 1
    return l

class Solution {
  public int maximizeSweetness(int[] sweetness, int k) {
    int l = 0, r = 0;
    for (int v : sweetness) {
      r += v;
    }
    while (l < r) {
      int mid = (l + r + 1) >> 1;
      if (check(sweetness, mid, k)) {
        l = mid;
      } else {
        r = mid - 1;
      }
    }
    return l;
  }

  private boolean check(int[] nums, int x, int k) {
    int s = 0, cnt = 0;
    for (int v : nums) {
      s += v;
      if (s >= x) {
        s = 0;
        ++cnt;
      }
    }
    return cnt > k;
  }
}

class Solution {
public:
  int maximizeSweetness(vector<int>& sweetness, int k) {
    int l = 0, r = accumulate(sweetness.begin(), sweetness.end(), 0);
    auto check = [&](int x) {
      int s = 0, cnt = 0;
      for (int v : sweetness) {
        s += v;
        if (s >= x) {
          s = 0;
          ++cnt;
        }
      }
      return cnt > k;
    };
    while (l < r) {
      int mid = (l + r + 1) >> 1;
      if (check(mid)) {
        l = mid;
      } else {
        r = mid - 1;
      }
    }
    return l;
  }
};

func maximizeSweetness(sweetness []int, k int) int {
  l, r := 0, 0
  for _, v := range sweetness {
    r += v
  }
  check := func(x int) bool {
    s, cnt := 0, 0
    for _, v := range sweetness {
      s += v
      if s >= x {
        s = 0
        cnt++
      }
    }
    return cnt > k
  }
  for l < r {
    mid := (l + r + 1) >> 1
    if check(mid) {
      l = mid
    } else {
      r = mid - 1
    }
  }
  return l
}

function maximizeSweetness(sweetness: number[], k: number): number {
  let l = 0;
  let r = sweetness.reduce((a, b) => a + b);
  const check = (x: number): boolean => {
    let s = 0;
    let cnt = 0;
    for (const v of sweetness) {
      s += v;
      if (s >= x) {
        s = 0;
        ++cnt;
      }
    }
    return cnt > k;
  };
  while (l < r) {
    const mid = (l + r + 1) >> 1;
    if (check(mid)) {
      l = mid;
    } else {
      r = mid - 1;
    }
  }
  return l;
}