สมมติว่าเรามีแท่งช็อกโกแลตหนึ่งแท่ง ประกอบด้วยชิ้นเล็กๆ (chunks) แต่ละชิ้นมีความหวาน (sweetness) กำหนดโดยรายการที่ชื่อว่า sweetness หากเราต้องการแบ่งช็อกโกแลตให้เพื่อน K คน เราจะเริ่มตัดแท่งช็อกโกแลตเป็น K+1 ชิ้น โดยใช้ K ครั้ง ตอนนี้แต่ละชิ้นประกอบด้วยชิ้นเล็กที่ติดกัน หากเราหยิบชิ้นที่มีความหวานรวมต่ำสุด และให้ชิ้นอื่นๆ แก่เพื่อน เราต้องหาความหวานรวมสูงสุดของชิ้นที่เราสามารถได้โดยการตัดช็อกโกแลตอย่างเหมาะสม
ดังนั้น หากอินพุทคือ 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
for i := 0 ถึงขนาดของ v:
ถ้า temp ≥ maxVal: counter++, temp := 0
ถ้า i == ขนาดของ v: break
temp := temp + v[i]
คืนค่า true เมื่อ counter ≥ cuts
จาก main method:
maxa := -1, n := ขนาดของ s
low := 0, high := 0
for i := 0 ถึง n-1: low := min(low, s[i]), high := high + s[i]
high++
while 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& 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& s, int k) {
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;
}
};
int main() {
Solution ob;
vector v = {1, 2, 3, 4, 5, 6, 7, 8, 9};
cout << (ob.maximizeSweetness(v, 5));
return 0;
}
อินพุต
{1,2,3,4,5,6,7,8,9}, 5
เอาต์พุต
6
