Hiểu bài toán

Bài toán giả lập việc một xe đưa thư di chuyển trên trục số (bưu điện tại 0) để chuyển thư đến N địa điểm với số lượng thư khác nhau. Xe có tải trọng tối đa K. Mục tiêu là tìm tổng quãng đường di chuyển最小 (bao gồm cả việc quay về bưu điện) để chuyển hết tất cả thư.

Mỗi chuyến đi, xe có thể chở tối đa K thư. Nếu chuyển hết thư tại một điểm hoặc hết chỗ chứa, xe có thể quay về bưu điện hoặc tiếp tục di chuyển đến các điểm khác cùng hướng. Do trục số thẳng, ta có thể chia bài toán thành hai bên độc lập: bên trái (x < 0) và bên phải (x > 0). Với mỗi bên, ta cần tối ưu hóa các chuyến đi.

Các cách tiếp cận

Cách Mô phỏng theo hướng từ điểm xa nhất về

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

struct duathu{
    int x, t;
};
bool ktra(const duathu &c, const duathu &d){
    return c.x > d.x;
}

long long side(vector<duathu> &v, int k){
    long long dist = 0;
    int m = v.size();
    int i = 0;
    while(i < m){
        while(i < m && v[i].t == 0){
            i++;
        }
        if(i == m) break;
        dist += 2 * abs(v[i].x);
        int cap = k;
        for(int j = i; j < m && cap > 0; j++){
            long long take = min(cap, v[j].t);
            cap -= take;
            v[j].t -= take;
        }
    }
    return dist;
}
int main(){
    int n, k;
    cin >> n >> k;
    vector<duathu> a(n);
    vector<duathu> l, r;
    for(int i = 0; i < n; i++){
        cin >> a[i].x >> a[i].t;
        if(a[i].x < 0){
            l.push_back({-a[i].x, a[i].t});
        }else{
            r.push_back({a[i].x, a[i].t});
        }
    }
    sort(l.begin(), l.end(), ktra);
    sort(r.begin(), r.end(), ktra);
    cout << side(l, k) + side(r, k) << endl;
    return 0;
}

• Time Complexity: O(N * maxtrips) trong đó maxtrips ~ T/K (Tổng thư). Với N=1000, T~800000, K=10000, số chuyến tối đa là 80. Số thao tác ~ 80 * 1000 = 80000, quá nhanh.
• Space Complexity: O(N)

Cách tiếp cận này chia bài toán thành hai bên trái và phải. Sau đó, với mỗi bên, ta sắp xếp các điểm theo thứ tự giảm dần của khoảng cách (điểm xa nhất trước). Ta lặp khi còn thư cần chuyển:

1. Chọn điểm xa nhất (đầu danh sách) còn thư. Đây là điểm mà xe sẽ đi xa nhất trong chuyến này.
2. Thêm quãng đường 2 * khoảng cách điểm đó (đi và về).
3. Duyệt từ điểm xa nhất này về điểm gần nhất, dồn尽可能 nhiều thư vào xe (tối đa K).
4. Giảm số thư cần chuyển tại các điểm đã lấy.
5. Lặp lại cho đến khi hết thư.

Ví dụ: Với các điểm [10 (175), 25 (20)] và K=100.

• Chuyến 1: Điểm xa nhất là 25. Đi 25 và về (50). Lấy 20 thư ở 25, còn chỗ 80. Lấy 80 thư ở 10. Hiện tại 10 còn 95 thư.
• Chuyến 2: Điểm xa nhất là 10. Đi 10 và về (20). Lấy 80 thư ở 10. Còn 15 thư.
• Chuyến 3: Điểm xa nhất là 10. Đi 10 và về (20). Lấy 15 thư ở 10. Tổng: 50 + 20 + 20 = 90.

Cách Tối ưu hóa bằng cách tính số chuyến đi

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

ll get(vector<pair<int,int>> &p, int K) {
    sort(p.begin(), p.end(), [&](auto &a, auto &b){
        return abs(a.first) > abs(b.first);
    });

    ll ans = 0;
    ll r = 0; 
    ll pre = 0;  

    for (auto [pos, mail] : p) {
        ll d = abs(pos);
        r += mail;
        ll trips = (r + K - 1) / K;   
        ll new_trips = trips - pre;
        if (new_trips > 0) {
            ans += new_trips * 2LL * d;  
            pre = trips;
        }
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, K;
    cin >> N >> K;
    vector<pair<int,int>> l, r;
    for (int i = 0; i < N; i++) {
        int x, t;
        cin >> x >> t;
        if (x < 0) l.push_back({x, t});
        else r.push_back({x, t});
    }

    ll res = get(l, K) + get(r, K);
    cout << res << "\n";
    return 0;
}

• Time Complexity: O(N log N) do sắp xếp.
• Space Complexity: O(N)

Phương pháp này dựa trên quan sát toán học. Với mỗi bên, ta sắp xếp các điểm theo khoảng cách giảm dần.

Giả sử ta có các điểm với khoảng cách giảm dần d1, d2, ..., dm. Gọi Si là tổng số thư từ điểm xa nhất đến điểm thứ i. Số chuyến đi tối thiểu để chuyển hết thư đến các điểm có khoảng cách >= di là ceil(S_i / K).

Quãng đường phát sinh khi ta xét đến điểm thứ i (khoảng cách di) là số chuyến đi mới cần thiết so với điểm trước đó, nhân với khoảng cách di (và nhân 2 cho lượt đi/về).

Công thức: ans += (ceil(Tổng thư đến điểm hiện tại / K) - ceil(Tổng thư đến điểm trước đó / K)) * 2 * d_i.

Giải thích:

• r là tổng thư tích lũy từ các điểm xa nhất đến điểm hiện tại.
• trips là số chuyến đi cần thiết để chuyển hết r thư.
• pre là số chuyến đi đã tính cho các điểm xa hơn.
• new_trips là số chuyến đi mới phát sinh khi thêm điểm hiện tại (và các điểm gần hơn) vào.
• Mỗi chuyến đi mới này đều phải đi xa đến d_i để tiện đường (vì xe phải đi qua điểm này để đến các điểm xa hơn), nên ta cộng dồn quãng đường vào d_i.

Cách Mô phỏng tối ưu (Quản lý chỗ trống)

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

ll solve_side(vector<pair<ll,ll>>& v, ll K) {
    // v: pair(distance, count), distances sorted descending
    ll res = 0;
    ll carry = 0; // chỗ còn lại trên lượt hiện tại (0..K-1)
    for (auto &p : v) {
        ll d = p.first;
        ll t = p.second;
        if (carry > 0) {
            // dùng carry để bớt số thư cần tới điểm này
            ll use = min(carry, t);
            t -= use;
            carry -= use;
        }
        if (t == 0) continue;
        // số lượt đầy (mỗi lượt chở K thư)
        ll full_trips = t / K;
        if (full_trips > 0) {
            res += 2LL * d * full_trips;
            t -= full_trips * K;
        }
        if (t > 0) {
            // một lượt thừa (không đầy) tới khoảng cách d
            res += 2LL * d;
            carry = K - t; // lượt này còn chỗ để phục vụ điểm gần hơn
            t = 0;
        }
    }
    return res;
}

int main() {
    // ... (truncated)

• Time Complexity: O(N log N)
• Space Complexity: O(N)

Cách tiếp cận này mô phỏng quá trình đi lại nhưng tối ưu hóa bằng cách quản lý chỗ trống (carry) còn lại của các chuyến đi.

1. Sắp xếp điểm theo khoảng cách giảm dần.
2. Duyệt từng điểm:
   • Nếu có chỗ trống từ chuyến đi trước (carry), dùng nó để chuyển thư cho điểm hiện tại trước.
   • Nếu vẫn còn thư ở điểm hiện tại:
     • Chia thành các chuyến đi đầy đủ (full trips): t / K. Mỗi chuyến đầy đủ đi xa nhất đến d (vì phải đi qua đây để đến các điểm xa hơn hoặc chỉ đơn giản là chuyến này chỉ phục vụ điểm này và về). Cộng 2 * d * full_trips vào kết quả.
     • Phần thư thừa t % K: Tạo ra một chuyến đi không đầy (partial trip). Chuyến này đi xa nhất đến d và về, tốn 2 * d. Chỗ trống còn lại K - t được lưu vào carry để dùng cho các điểm gần hơn.

Ví dụ: K=100, điểm A (10, 175), điểm B (25, 20).

• Xét B (25, 20): Chưa có carry. T Full = 0. T Partial = 20. Res += 2*25 = 50. Carry = 80.
• Xét A (10, 175): Dùng carry 80. Còn 95 thư. T Full = 95/100 = 0. T Partial = 95. Res += 2*10 = 20. Carry = 5. Đáp án: 50 + 20 = 90.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Bài toán tách rời thành 2 bên trái/phải.
• Luôn ưu tiên xử lý điểm xa nhất trước (greedy).
• Tổng quãng đường là tổng của các chuyến đi, mỗi chuyến đi tính quãng đường từ 0 đến điểm xa nhất và về 0.

Lỗi thường gặp

• Sai đơn vị (quên nhân đôi quãng đường đi và về).
• Xử lý số chuyến đi không đúng (sai phép chia lấy nguyên).
• Lộn xộn thứ tự xử lý các điểm.