leetcode 1231 - Divide Chocolate

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
public:
int maximizeSweetness(vector<int>& sweetness, int K) {
int left = 1, right = 0;

for (int s : sweetness)
right += s;

while (left <= right) {
int mid = left + (right - left) / 2;

if (valid(sweetness, K, mid))
left = mid + 1;
else
right = mid - 1;
}

return left - 1;
}

bool valid(vector<int> &sweetness, int K, int m) {
int count = 0;
int total = 0;

for (int s : sweetness) {
total += s;
if (total >= m) {
if (++count > K)
return true;
total = 0;
}
}

return false;
}
};