Hướng giải của Phân Hoạch Đoạn Con

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

Hướng dẫn giải: Phân Hoạch Đoạn Con

Phân tích bài toán

Bài toán yêu cầu phân chia đoạn con \(A[L..R]\) thành ít đoạn con nhất có tổng mỗi đoạn \(\le M\).

  1. Thiết lập bước nhảy: Từ vị trí \(i\), nếu ta chọn đoạn con có tổng \(\le M\) dài nhất có thể, điểm tiếp theo bắt đầu đoạn mới sẽ là \(j > i\) nhỏ nhất thỏa mãn \(A_i + \dots + A_{j-1} > M\) (tức là \(A_i + \dots + A_{j-1} \ge M + 1\)). Ta tìm mảng chuyển trạng thái nxt[i] = j bằng hai con trỏ trong \(O(N)\) và dựng bảng Binary Lifting up[i][j].
  2. Kiểm tra tính hợp lệ: Nếu trong đoạn \([L, R]\) tồn tại bất kỳ phần tử nào \(> M\), kết quả chắc chắn là -1. Ta kiểm tra điều này trong \(O(1)\) bằng Sparse Table RMQ (tiền xử lý trong \(O(N \log N)\)).
  3. Thực hiện truy vấn: Tìm số bước nhảy tối thiểu từ \(L\) để đạt tới hoặc vượt qua vị trí \(R + 1\). Sử dụng nhảy nhị phân tương tự bài Phủ Đoạn.
Độ phức tạp
  • Thời gian: \(O(N \log N)\) tiền xử lý và \(O(\log N)\) mỗi truy vấn.
  • Không gian: \(O(N \log N)\) bộ nhớ.
Mã nguồn C++ mẫu
#include <bits/stdc++.h>
using namespace std;

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

    int K = 20;
    vector<vector<long long>> st(n, vector<long long>(K));
    for (int i = 0; i < n; i++) st[i][0] = a[i];
    for (int j = 1; j < K; j++) {
        for (int i = 0; i + (1 << j) <= n; i++) {
            st[i][j] = max(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
        }
    }

    auto query_max = [&](int L, int R) {
        int len = R - L + 1;
        int k = __lg(len);
        return max(st[L][k], st[R - (1 << k) + 1][k]);
    };

    vector<int> nxt(n + 1);
    nxt[n] = n;
    int r = 0;
    long long sum_val = 0;
    for (int i = 0; i < n; i++) {
        while (r < n && sum_val <= m) {
            sum_val += a[r];
            r++;
        }
        if (sum_val > m) {
            nxt[i] = r - 1;
        } else {
            nxt[i] = n;
        }
        sum_val -= a[i];
    }

    int LOG = 21;
    vector<vector<int>> up(n + 1, vector<int>(LOG));
    for (int i = 0; i <= n; i++) {
        up[i][0] = nxt[i];
    }
    for (int j = 1; j < LOG; j++) {
        for (int i = 0; i <= n; i++) {
            up[i][j] = up[up[i][j - 1]][j - 1];
        }
    }

    while (q--) {
        int l, r_q;
        cin >> l >> r_q;
        l--; r_q--;
        if (query_max(l, r_q) > m) {
            cout << -1 << "\n";
            continue;
        }
        int curr = l;
        int steps = 0;
        int target = r_q + 1;
        for (int j = LOG - 1; j >= 0; j--) {
            if (up[curr][j] < target) {
                steps += (1 << j);
                curr = up[curr][j];
            }
        }
        curr = up[curr][0];
        steps += 1;
        cout << steps << "\n";
    }
    return 0;
}

Nhận xét

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