Hướng giải của Phân sách cho K sinh viên

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: Phân sách cho K sinh viên

Ý tưởng

Bài toán này về bản chất giống Chia mảng lớn nhất (bsa-05):

  • Tìm \(M\) nhỏ nhất sao cho có thể chia \(N\) cuốn sách thành \(\le K\) đoạn liên tiếp, mỗi đoạn có tổng \(\le M\).

Với \(M\) cho trước, ta gom sách: bắt đầu đoạn mới mỗi khi cộng thêm xấp tiếp theo vượt quá \(M\). Số đoạn là hàm đơn điệu giảm theo \(M\).

Thuật toán

  • Cận dưới: \(\max p_i\) (xấp dày nhất).
  • Cận trên: \(\sum p_i\).
  • Thử \(mid = \lfloor (lo + hi)/2 \rfloor\); đếm đoạn; so sánh với \(K\).

Độ phức tạp

  • Thời gian: \(O(N \log(\sum p_i))\).
  • Bộ nhớ: \(O(N)\).

Mã nguồn tham khảo

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int N, K;
    cin >> N >> K;
    vector<int> p(N);
    long long sum = 0, mx = 0;
    for (int i = 0; i < N; i++) {
        cin >> p[i];
        sum += p[i];
        mx = max(mx, (long long)p[i]);
    }
    long long lo = mx, hi = sum;
    while (lo < hi) {
        long long mid = lo + (hi - lo) / 2;
        int cnt = 1;
        long long cur = 0;
        for (int x : p) {
            if (cur + x <= mid) cur += x;
            else { cnt++; cur = x; }
        }
        if (cnt <= 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.