用C ++划分Chocolate
假设我们有一个由一些大块组成的巧克力棒。在每个块中,它都有自己的甜味,该甜味由称为甜味的列表给出。如果我们想在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