## 1231. Divide Chocolate

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 = 5Output:6Explanation: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 = 8Output:1Explanation: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 = 2Output:5Explanation:You can divide the chocolate to [1,2,2], [1,2,2], [1,2,2]

**Constraints:**

`0 <= K < sweetness.length <= 10^4`

`1 <= sweetness[i] <= 10^5`

## Rust Solution

```
struct Solution;
impl Solution {
fn maximize_sweetness(sweetness: Vec<i32>, k: i32) -> i32 {
let mut left = 1;
let mut right = 1_000_000_000;
while left < right {
let mid = (left + right + 1) / 2;
let mut cut = 0;
let mut cur = 0;
for &x in &sweetness {
cur += x;
if cur >= mid {
cut += 1;
cur = 0;
}
}
if cut > k {
left = mid;
} else {
right = mid - 1;
}
}
left
}
}
#[test]
fn test() {
let sweetness = vec![1, 2, 3, 4, 5, 6, 7, 8, 9];
let k = 5;
let res = 6;
assert_eq!(Solution::maximize_sweetness(sweetness, k), res);
let sweetness = vec![5, 6, 7, 8, 9, 1, 2, 3, 4];
let k = 8;
let res = 1;
assert_eq!(Solution::maximize_sweetness(sweetness, k), res);
let sweetness = vec![5, 6, 7, 8, 9, 1, 2, 3, 4];
let k = 8;
let res = 1;
assert_eq!(Solution::maximize_sweetness(sweetness, k), res);
let sweetness = vec![1, 2, 2, 1, 2, 2, 1, 2, 2];
let k = 2;
let res = 5;
assert_eq!(Solution::maximize_sweetness(sweetness, k), res);
}
```

Having problems with this solution? Click here to submit an issue on github.