สมมติว่าเรามีรายการตัวเลขที่เรียกว่า nums และอีกค่าหนึ่งคือ k เราสามารถแบ่งรายการออกเป็น k รายการย่อยที่ไม่ว่างเปล่า เราต้องหาผลรวมต่ำสุดของ k รายการย่อย
ดังนั้น หากอินพุตมีค่าเท่ากับ nums =[2, 4, 3, 5, 12] k =2 ผลลัพธ์จะเป็น 14 เนื่องจากเราสามารถแบ่งรายการได้ดังนี้ [2, 4, 3, 5] และ [ 12].
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
กำหนดฟังก์ชัน ok() ซึ่งจะใช้อาร์เรย์ v, k, x,
-
cnt :=0, ผลรวม :=0
-
สำหรับแต่ละองค์ประกอบ i ใน v -
-
ถ้า sum + i> x แล้ว −
-
ผลรวม :=ผม
-
(เพิ่มขึ้นอีก 1)
-
-
มิฉะนั้น
-
sum :=sum + i
-
-
-
คืนค่า จริง เมื่อ cnt <=k ไม่เช่นนั้น เท็จ
-
จากวิธีหลัก ให้ทำดังต่อไปนี้ −
-
ต่ำ :=0, ถอยหลัง :=0, สูง :=0
-
สำหรับแต่ละองค์ประกอบ i เป็น nums
-
สูง :=สูง + ผม
-
ret :=ret + ผม
-
ต่ำ :=สูงสุดของค่าต่ำสุดและ i
-
-
ในขณะที่ต่ำ <=สูง ทำ -
-
กลาง :=ต่ำ + (สูง - ต่ำ) / 2
-
ถ้า ok(nums, k - 1, mid) เป็นจริง −
-
ret :=กลาง
-
สูง :=กลาง - 1
-
-
มิฉะนั้น
-
ต่ำ :=กลาง + 1
-
-
-
รีเทิร์น
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
#include <bits/stdc++.h>
using namespace std;
bool ok(vector <int>& v, int k, int x){
int cnt = 0;
int sum = 0;
for(int i : v){
if(sum + i > x){
sum = i;
cnt++;
}
else{
sum += i;
}
}
return cnt <= k;
}
int solve(vector<int>& nums, int k) {
int low = 0;
int ret = 0;
int high = 0;
for(int i : nums){
high += i;
ret += i;
low = max(low, i);
}
while(low <= high){
int mid = low + ( high - low) / 2;
if(ok(nums, k - 1, mid)){
ret = mid;
high = mid - 1;
}
else{
low = mid + 1;
}
}
return ret;
}
int main(){
vector<int> v = {2, 4, 3, 5, 12};
int k = 2;
cout << solve(v, k);
} อินพุต
{2, 4, 3, 5, 12}, 2 ผลลัพธ์
14
