Hiểu bài toán

Bài toán mô phỏng việc một xe ô tô (Bờm) đi trên một con đường có tốc độ tối đa cho phép. Con đường được chia thành N đoạn, mỗi đoạn có chiều dài và giới hạn tốc độ khác nhau. Hành trình của Bờm được chia thành M đoạn, mỗi đoạn có chiều dài và tốc độ di chuyển thực tế. Nhiệm vụ là tìm giá trị lớn nhất của sự chênh lệch giữa tốc độ thực tế và tốc độ cho phép (tốc độ thực tế - tốc độ cho phép) tại bất kỳ điểm nào trên hành trình. Nếu Bờm không vượt quá tốc độ cho phép ở bất kỳ đâu, kết quả là 0.

Dữ liệu nhập:

• L: Chiều dài toàn bộ con đường.
• N: Số đoạn của con đường.
• M: Số đoạn của hành trình.
• Tiếp theo là N cặp số (chiều dài, tốc độ cho phép).
• Tiếp theo là M cặp số (chiều dài, tốc độ thực tế).

Dữ liệu xuất:

• Một số nguyên là giá trị chênh lệch tốc độ lớn nhất.

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

Cách Mô phỏng chi tiết (Duyệt theo từng mét/đơn vị)

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

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

    // Tối ưu hóa nhập xuất
    // freopen("speed.inp", "r", stdin);
    // freopen("speed.out", "w", stdout);

    long long L;
    int N, M;
    cin >> L >> N >> M;

    // Dùng mảng kích thước L+1 để lưu giới hạn tốc độ cho từng đơn vị khoảng cách
    vector<int> limit(L + 1);
    long long pos = 1;
    for(int i = 0; i < N; i++) {
        long long d, v;
        cin >> d >> v;
        // Gán tốc độ cho từng đơn vị khoảng cách trong đoạn d
        for(long long x = pos; x < pos + d; x++)
            limit[x] = v;
        pos += d;
    }

    // Tương tự cho hành trình của Bờm
    vector<int> run(L + 1);
    pos = 1;
    for(int i = 0; i < M; i++) {
        long long d, v;
        cin >> d >> v;
        for(long long x = pos; x < pos + d; x++)
            run[x] = v;
        pos += d;
    }

    int ans = 0;
    // Duyệt qua từng đơn vị khoảng cách để tìm max
    for(int i = 1; i <= L; i++)
        ans = max(ans, run[i] - limit[i]);

    if(ans < 0) ans = 0;
    cout << ans;
}

• Time Complexity: O(L + N + M)
• Space Complexity: O(L)

Phương pháp này phân chia chi tiết con đường và hành trình thành từng đơn vị khoảng cách (ví dụ: từng mét). Nó tạo ra hai mảng limit và run, trong đó limit[i] là tốc độ cho phép tại mét thứ i, và run[i] là tốc độ của Bờm tại đó. Sau đó, duyệt qua các mảng này để tính toán chênh lệch tốc độ.

• Ưu điểm: Dễ hiểu, mô phỏng sát thực tế.
• Nhược điểm: Yêu cầu bộ nhớ O(L). Nếu L rất lớn (ví dụ 10^9), phương pháp này không khả thi về bộ nhớ và thời gian.

Cách Mô phỏng theo đoạn (Two Pointers)

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

int main() {
    ifstream fin("SPEED.INP");
    ofstream fout("SPEED.OUT");

    int L, N, M;
    fin >> L >> N >> M;

    vector<pair<int,int>> road(N);
    for(int i=0;i<N;i++) fin >> road[i].first >> road[i].second;

    vector<pair<int,int>> journey(M);
    for(int i=0;i<M;i++) fin >> journey[i].first >> journey[i].second;

    int i = 0, j = 0;
    int max_over = 0;
    // Khởi tạo chiều dài còn lại của đoạn hiện tại
    int len_i = road[i].first, len_j = journey[j].first;

    while(i < N && j < M){
        // Lấy khoảng cách nhỏ nhất giữa hai đoạn đang xét
        int d = min(len_i, len_j);

        // Tính toán chênh lệch tốc độ
        int over = journey[j].second - road[i].second;
        if(over > 0) max_over = max(max_over, over);

        // Trừ khoảng cách đã đi được
        len_i -= d;
        len_j -= d;

        // Nếu đoạn road hiện tại đã đi hết, chuyển sang đoạn tiếp theo
        if(len_i == 0) { 
            i++; 
            if(i < N) len_i = road[i].first; 
        }
        // Nếu đoạn journey hiện tại đã đi hết, chuyển sang đoạn tiếp theo
        if(len_j == 0) { 
            j++; 
            if(j < M) len_j = journey[j].first; 
        }
    }

    fout << max_over << "\n";
}

• Time Complexity: O(N + M)
• Space Complexity: O(N + M)

Đây là phương pháp tối ưu nhất. Thay vì duyệt chi tiết từng mét, ta duyệt theo các đoạn.

Hai con trỏ i và j đại diện cho chỉ số của đoạn đường hiện tại và đoạn hành trình hiện tại. Ta dùng biến len_i và len_j để theo dõi phần còn lại của các đoạn này.

Vòng lặp thực hiện:

1. Xác định khoảng cách nhỏ nhất (d) có thể đi mà không vượt quá một trong hai đoạn hiện tại.
2. Tính chênh lệch tốc độ trong khoảng d này (vì tốc độ là hằng số trong đoạn).
3. Cập nhật max_over nếu cần.
4. Trừ d khỏi len_i và len_j.
5. Nếu một đoạn hết, chuyển sang đoạn tiếp theo.

Phương pháp này chỉ duyệt qua N và M đoạn, rất hiệu quả.

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

Bài học kinh nghiệm

• Vấn đề có thể được chia thành các đoạn con (segments) mà tốc độ là hằng số.
• Tốc độ thực tế và tốc độ cho phép có thể được xử lý đồng thời bằng cách so sánh các đoạn hiện tại của cả hai.
• Giá trị chênh lệch tốc độ chỉ cần được kiểm tra tại các điểm giao nhau giữa các đoạn của con đường và các đoạn của hành trình.

Lỗi thường gặp

• Lầm tưởng rằng cần phải mô phỏng từng mét (hoặc centimet) một, dẫn đến giải thuật quá chậm hoặc hao tốn bộ nhớ đối với L lớn.
• Quên xử lý trường hợp chênh lệch tốc độ âm (kết quả phải là 0 nếu không có sự vượt quá tốc độ).
• Lỗi Off-by-one: Duyệt sai số lượng đoạn hoặc sai chỉ số mảng khi chia đôi các đoạn.