Lời giải: Xe tải chở hàng

Ý tưởng

Gọi \(C\) là sức chở của xe. Nếu \(C\) càng lớn thì số ngày cần dùng càng ít. Vì vậy hàm kiểm tra:

\[ f(C) = \text{có thể giao hết trong } D \text{ ngày với sức chở } C \text{ hay không} \]

có tính đơn điệu (nếu \(C\) đủ thì \(C+1\) cũng đủ), ta tìm \(C\) nhỏ nhất thỏa mãn $f(C) = $ đúng.

Thuật toán

Với mỗi sức chở thử \(C\), ta duyệt qua các gói hàng theo thứ tự và tính số ngày cần dùng:

• Khởi đầu: ngày \(1\), tải hiện tại = \(0\).
• Với mỗi gói \(w_i\): nếu tải hiện tại \(+ w_i \le C\) thì cộng vào; ngược lại mở ngày mới, đặt gói này làm gói đầu của ngày mới.
• Kiểm tra số ngày dùng \(\le D\).

Tìm kiếm

• Cận dưới: \(\max_i w_i\) (ít nhất phải chở được gói nặng nhất).
• Cận trên: \(\sum_i w_i\) (chở hết trong \(1\) ngày).
• Mỗi bước thu hẹp một nửa khoảng tìm kiếm.

Độ phức tạp

• Thời gian: \(O(N \log S)\) với \(S = \sum w_i\).
• Bộ nhớ: \(O(N)\).

Mã nguồn tham khảo

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

bool check(const vector<int>& w, int cap, int D) {
    long long cur = 0;
    int days = 1;
    for (int x : w) {
        if (cur + x <= cap) cur += x;
        else { days++; cur = x; }
    }
    return days <= D;
}

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