Chương trình tìm tổng lớn nhất nhỏ nhất của k danh sách con trong C++

Mô tả bài toán

Cho danh sách số nums và số k. Chia danh sách thành k danh sách con không rỗng. Tìm giá trị nhỏ nhất của tổng lớn nhất trong các danh sách con đó.

Ví dụ: nums = [2, 4, 3, 5, 12], k = 2 → kết quả 14 (chia thành [2,4,3,5] và [12]).

Giải thuật

1. Hàm ok(v, k, x): kiểm tra có thể chia v thành ≤ k đoạn với mỗi đoạn tổng ≤ x.
   • cnt = 0, sum = 0.
   • Duyệt từng phần tử i trong v:
     • Nếu sum + i > x: sum = i, cnt++.
     • Ngược lại: sum += i.
   • Trả về true nếu cnt ≤ k.
2. Trong hàm chính:
   • low = max phần tử, high = tổng tất cả, ret = high.
   • Nhị phân trên [low, high]:
     • mid = (low + high) / 2.
     • Nếu ok(nums, k-1, mid) thì ret = mid, high = mid - 1; ngược lại low = mid + 1.
   • Trả về ret.

Ví dụ minh họa (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;
}

Đầu vào

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

Đầu ra

14