Hướng giải của Chia mảng tối ưu

Nhớ rằng hướng dẫn giải này chỉ nên sử dụng khi bế tắc, và tuyệt đối không nên sao chép mã nguồn kèm theo. Hãy tôn trọng tác giả bài tập và người viết hướng dẫn giải.
Nộp mã nguồn lời giải chính thức trước khi giải bài tập đó có thể khiến bạn bị ban.

Tác giả: kienadmin

Để chia mảng thành \(K\) mảng con liên tiếp sao cho tổng lớn nhất là nhỏ nhất: Ta thực hiện Tìm kiếm nhị phân trên giá trị tổng lớn nhất \(S\).

  • Nghiệm \(S\) khả thi sẽ nằm trong khoảng \([\max(A), \sum A]\):
    • Cận dưới: tổng mảng con không thể nhỏ hơn phần tử lớn nhất trong mảng ban đầu (vì mỗi phần tử thuộc về 1 mảng con).
    • Cận trên: chia mảng thành 1 đoạn duy nhất (\(K=1\)).

Hàm kiểm tra \(P(S)\): "Có thể chia mảng thành tối đa \(K\) mảng con liên tiếp sao cho tổng mỗi mảng con không vượt quá \(S\) không?"

  • Ta duyệt qua mảng từ trái sang phải, duy trì tổng tích lũy hiện tại.
  • Nếu thêm phần tử tiếp theo vào mảng con hiện tại làm tổng vượt quá \(S\), ta phải tạo mảng con mới bắt đầu từ phần tử này, đồng thời tăng số lượng mảng con đã chia lên 1.
  • Nếu số lượng mảng con vượt quá \(K\), trả về false. Ngược lại, trả về true.

Tìm kiếm nhị phân:

  • Nếu \(P(mid) = true\): giá trị tổng \(mid\) khả thi, ta thử tìm tổng nhỏ hơn bằng cách gán hi = mid.
  • Nếu \(P(mid) = false\): giá trị tổng \(mid\) không khả thi, ta phải tăng tổng lên bằng cách gán lo = mid + 1.

Độ phức tạp: \(O(N \log(\sum A))\).

Xem code mẫu C++ 
#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>

using namespace std;

bool canSplit(const vector<long long>& a, int k, long long max_sum) {
    int groups = 1;
    long long current_sum = 0;
    for (long long val : a) {
        if (current_sum + val <= max_sum) {
            current_sum += val;
        } else {
            groups++;
            current_sum = val;
            if (groups > k) return false;
        }
    }
    return true;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, k;
    if (!(cin >> n >> k)) return 0;
    vector<long long> a(n);
    long long max_val = 0;
    long long sum_val = 0;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        max_val = max(max_val, a[i]);
        sum_val += a[i];
    }

    long long lo = max_val, hi = sum_val;
    long long ans = sum_val;
    while (lo <= hi) {
        long long mid = lo + (hi - lo) / 2;
        if (canSplit(a, k, mid)) {
            ans = mid;
            hi = mid - 1;
        } else {
            lo = mid + 1;
        }
    }
    cout << ans << "\n";
    return 0;
}

Nhận xét

Không có ý kiến tại thời điểm này.