โปรแกรมหาผลรวมสูงสุดต่ำสุดของ k ส่วนย่อยใน C++

สมมติว่าเรามีรายการตัวเลข nums และค่า k เราสามารถแบ่งรายการเป็น k ส่วนย่อยที่ไม่ว่างเปล่า ต้องการหาค่าต่ำสุดของ "ผลรวมสูงสุด" ระหว่าง k ส่วนนั้น

ตัวอย่าง: nums = [2, 4, 3, 5, 12], k = 2 ผลลัพธ์คือ 14 เพราะแบ่งเป็น [2, 4, 3, 5] (ผลรวม 14) และ [12] (ผลรวม 12) ค่าสูงสุดคือ 14

ขั้นตอนการแก้ปัญหา

1. สร้างฟังก์ชัน ok(v, k, x) ตรวจสอบว่าแบ่งได้หรือไม่ด้วยขีดจำกัด x:
   • cnt := 0, sum := 0
   • วนทุกองค์ประกอบ i ใน v:
     • ถ้า sum + i > x: sum = i, cnt++
     • มิฉะนั้น: sum += i
   • คืนค่า true ถ้า cnt <= k
2. ในฟังก์ชันหลัก:
   • low := ค่าสูงสุดใน nums, high := ผลรวมทั้งหมด, ret := high
   • Binary Search ระหว่าง low ถึง high:
     • mid = low + (high - low) / 2
     • ถ้า ok(nums, k-1, mid) จริง: ret = mid, high = mid - 1
     • มิฉะนั้น: low = mid + 1
   • คืนค่า ret

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

bool ok(vector<int>& v, int k, int x) {
    int cnt = 0, 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, ret = 0, 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);
    return 0;
}

อินพุต

{2, 4, 3, 5, 12}, 2

เอาต์พุต

14