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

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.

Lời giải: Chia mảng

Ý tưởng

Với mỗi tổng tối đa \(M\), ta xác định số mảng con cần thiết: bắt đầu mảng mới mỗi khi cộng phần tử tiếp theo vượt quá \(M\). Số mảng con là một hàm đơn điệu giảm theo \(M\) (càng \(M\) lớn, càng ít mảng con). Ta tìm \(M\) nhỏ nhất sao cho số mảng con \(\le K\).

Thuật toán

  • Cận dưới: \(\max a_i\) (ít nhất một mảng con chứa phần tử lớn nhất).
  • Cận trên: \(\sum a_i\) (một mảng con gồm cả dãy).
  • Với \(mid\) giữa: đếm số mảng con. Nếu \(\le K\): \(hi = mid\), nếu \(>K\): \(lo = mid + 1\).

Độ phức tạp

  • Mỗi lần kiểm tra: \(O(N)\).
  • Tổng: \(O(N \log(\sum a_i))\).

Mã nguồn tham khảo

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

int cntParts(const vector<int>& a, long long M) {
    int parts = 1;
    long long cur = 0;
    for (int x : a) {
        if (cur + x <= M) cur += x;
        else { parts++; cur = x; }
    }
    return parts;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int N, K;
    cin >> N >> K;
    vector<int> a(N);
    long long sum = 0, mx = 0;
    for (int i = 0; i < N; i++) {
        cin >> a[i];
        sum += a[i];
        mx = max(mx, (long long)a[i]);
    }
    long long lo = mx, hi = sum;
    while (lo < hi) {
        long long mid = lo + (hi - lo) / 2;
        if (cntParts(a, mid) <= K) hi = mid;
        else lo = mid + 1;
    }
    cout << lo << "\n";
    return 0;
}

Nhận xét

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