假设我们有一个由一些大块组成的巧克力棒。在每个块中，它都有自己的甜味，该甜味由称为甜味的列表给出。如果我们想在K个朋友之间共享巧克力，那么我们就开始使用K切口将巧克力条切成K + 1块，现在每块都包含一些连续的块。如果我们以最小的总甜度取出一块，然后将其他块交给我们的朋友。我们必须找到通过最佳切割巧克力条可获得的最大总甜度。
因此，如果输入像甜度= [1,2,3,4,5,6,7,8,9]，K = 5，则输出将为6，因为您可以将巧克力除以[1,2 ，3]，[4,5]，[6]，[7]，[8]，[9]这些片段。
为了解决这个问题，我们将遵循以下步骤-
定义一个函数ok()，它将采用数组v，cuts，maxVal，
计数器：= 0，温度：= 0
对于初始化i：= 0，当i <= v的大小时，更新（将i增加1），执行-
从循环中出来
（将计数器增加1）
温度：= 0
如果temp> = maxVal，则
如果i与v的大小相同，则-
temp：= temp + v [i]
当counter> = cuts时返回true
从主要方法执行以下操作：
最大值：= -1
n：= s的大小
低：= 0，高：= 0
对于初始化i：= 0，当i <n时，更新（将i增加1），执行-
低：=低和s [i]的最小值
高：=高+ s [i]
（增加1）
当低<高时，执行-
高：=中-1
低：=中
中：=低+（高-低+ 1）/ 2
如果ok（s，k + 1，mid）为真，则-
除此以外
返回低
让我们看下面的实现以更好地理解-
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool ok(vector <int> v, int cuts, int maxVal){
int counter = 0;
int temp = 0;
for (int i = 0; i <= v.size(); i++) {
if (temp >= maxVal) {
counter++;
temp = 0;
}
if (i == v.size()) {
break;
}
temp += v[i];
}
return counter >= cuts;
}
int maximizeSweetness(vector<int>& s, int k) {
int maxa = -1;
int n = s.size();
int low = 0;
int high = 0;
for (int i = 0; i < n; i++) {
low = min(low, s[i]);
high += s[i];
}
high++;
while (low < high) {
int mid = low + (high - low + 1) / 2;
if (ok(s, k + 1, mid))
low = mid;
else
high = mid - 1;
}
return low;
}
};
main(){
Solution ob;
vector<int> v = {1,2,3,4,5,6,7,8,9};
cout << (ob.maximizeSweetness(v, 5));
}{1,2,3,4,5,6,7,8,9}, 5输出结果
6