Hiểu bài toán

Bài toán mô tả một bến xe buýt có chuyến đầu tiên khởi hành lúc thời điểm $T0$, và các chuyến tiếp theo cách đều nhau mỗi $D$ đơn vị thời gian. Có $N$ học sinh đến bến tại các thời điểm $Si$. Mỗi học sinh sẽ lên chuyến xe buýt đầu tiên đến không sớm hơn thời điểm họ đến. Yêu cầu là xác định số thứ tự của chuyến xe buýt mà từng học sinh sẽ lên.

Ví dụ: Nếu $T_0=8, D=5$, các chuyến xe đến vào các thời điểm: 8, 13, 18, 23, 28,... Nếu học sinh đến lúc 15, học sinh sẽ bỏ lỡ chuyến 13 (quá sớm) và sẽ lên chuyến 18. Số hiệu chuyến xe cần tính là 4 (chuyến đầu là số 1).

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

Cách Công thức quỹ đạo trực tiếp

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

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

    int N;
    long long D, T0;
    cin >> N >> D >> T0;

    vector<long long> S(N);
    for (int i = 0; i < N; i++) {
        cin >> S[i];
    }

    for (int i = 0; i < N; i++) {
        long long s = S[i];
        if (s <= T0) {
            // Nếu đến trước hoặc ngay lúc xe đầu tiên
            cout << 1;
        } else {
            // Tính số khoảng cách D cần thiết để vượt qua s
            // k = ceil((s - T0) / D)
            long long k = (s - T0 + D - 1) / D;
            // Chuyến thứ k+1 (vì chuyến đầu là T0 + 0*D)
            cout << (k + 1);
        }
        if (i + 1 < N) cout << ' ';
    }
    cout << '\n';

    return 0;
}

• Time Complexity: O(N)
• Space Complexity: O(N) (hoặc O(1) nếu xử lý từng phần tử)

Đây là phương pháp hiệu quả nhất, dựa trên giả định rằng các chuyến xe chạy đều đặn.

• Nếu $Si \le T0$, học sinh lên chuyến đầu tiên (số 1).
• Nếu $Si > T0$, ta cần tìm số nguyên $k$ nhỏ nhất sao cho $T0 + k \times D \ge Si$.
• Biến đổi bất phương trình: $k \times D \ge Si - T0 \Rightarrow k \ge \frac{Si - T0}{D}$.
• Vì $k$ là số nguyên, ta lấy $k = \lceil \frac{S_i - T0}{D} \rceil$. Công thức tính số nguyên dương nhỏ nhất lớn hơn hoặc bằng một phân số là ceil(a/b) = (a + b - 1) / b (với số nguyên dương).
• Số hiệu chuyến xe là $k + 1$ (chuyến đầu tiên tương ứng với $k=0$).

Cách Mô phỏng giả lập

#include <iostream>
#include <vector>
using namespace std;
int main() {
    int n, D, T0;
    cin >> n >> D >> T0;
    vector<int> s(n);
    for (int i = 0; i < n; i++) {
        cin >> s[i];
    }
    long long current_time = T0;
    int bus_index = 1;

    // Lưu ý: Cách này chỉ hiệu quả nếu sắp xếp học sinh theo thời gian đến.
    // Nếu input không sắp xếp, ta phải xử lý từng người hoặc dùng mảng.
    // Dưới đây là cách xử lý từng người độc lập bằng cách 'đoán' số chuyến.
    // (Giải pháp sử dụng vòng lặp while để mô phỏng)

    for(int i = 0; i < n; i++) {
        long long arrival = s[i];
        long long my_bus_time = T0;
        int my_bus_index = 1;
        while(my_bus_time < arrival) {
            my_bus_time += D;
            my_bus_index++;
        }
        cout << my_bus_index << (i == n - 1 ? "" : " ");
    }
    cout << endl;
    return 0;
}

• Time Complexity: O(N * (k)) - phụ thuộc vào khoảng cách thời gian, tối đa O(N * 10^6/D)
• Space Complexity: O(N)

Phương pháp này mô phỏng lại quá trình các chuyến xe đến.

• Với mỗi học sinh có thời gian đến $Si$, ta bắt đầu từ chuyến đầu tiên $T0$.
• Nếu $T0 < Si$, ta chuyển sang chuyến tiếp theo $T_0 + D$ và tăng số thứ tự chuyến lên 1.
• Lặp lại cho đến khi tìm được chuyến xe có thời gian đến lớn hơn hoặc bằng $S_i$.
• Phương pháp này đúng logic nhưng chậm hơn nhiều so với công thức trực tiếp vì phải lặp lại quá nhiều lần nếu $S_i$ lớn và $D$ nhỏ.

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

Bài học kinh nghiệm

• Bài toán có tính chất 'xích đạo' (arithmetic progression). Không cần mô phỏng từng giây mà có thể dùng công thức toán học để tìm số chuyến.
• Công thức tính số nguyên nhỏ nhất lớn hơn hoặc bằng một phân số (ceil) là chìa khóa: k = (a + b - 1) / b với số nguyên dương.

Lỗi thường gặp

• Lỗi số nguyên (Integer Overflow): Nếu $S_i$ lên tới $10^6$ và $T0, D$ nhỏ, phép tính (s - T0) có thể vượt quá giới hạn của kiểu int nếu dùng 32-bit. Cần sử dụng long long.
• Lỗi làm tròn sai: Khi tính số chuyến cần thêm, không được dùng phép chia số nguyên / thông thường vì nó làm tròn xuống, dẫn đến sai trường hợp chia hết (vd: 10/5 = 2, nhưng cần 1 chuyến nếu đã ở đúng giờ). Phải dùng công thức ceil.