資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學C++巧克力分割
假設我們有一塊巧克力，它由一些小塊組成。每塊小巧克力的甜度由名為sweetness的列表給出。如果我們要將巧克力分給K個朋友，我們使用K個切割將巧克力分成K+1塊，現在每塊都包含一些連續的小塊。如果我們取出甜度總和最小的部分，並將其他部分送給我們的朋友，我們必須找到透過最佳切割巧克力可以獲得的最大甜度總和。
因此，如果輸入類似於 sweetness = [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。
計數器 counter := 0，臨時變數 temp := 0
對於初始化 i := 0，當 i <= v 的大小，更新 (i 增加 1)，執行：
如果 temp >= maxVal，則
(計數器增加 1)
temp := 0
如果 i 等於 v 的大小，則：
退出迴圈
temp := temp + v[i]
如果計數器 counter >= cuts，則返回 true
在主方法中執行以下操作
maxa := -1
n := s 的大小
low := 0，high := 0
對於初始化 i := 0，當 i < n，更新 (i 增加 1)，執行：
low := low 和 s[i] 的最小值
high := high + s[i]
(high 增加 1)
當 low < high 時，執行：
mid := low + (high - low + 1) / 2
如果 ok(s, k + 1, mid) 為真，則：
low := mid
否則
high := mid - 1
返回 low
讓我們看看下面的實現來更好地理解：
示例
#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
瀏覽量：319
