1. Phân tích đề bài
- Mục tiêu: Tìm thời gian sớm nhất để người thứ mua xong vé.
- Quy tắc phục vụ:
- Phục vụ theo nhóm (đợt), mỗi nhóm tối đa người.
- Thời gian bắt đầu một đợt = .
- Điều kiện quan trọng: Tất cả mọi người trong một nhóm phải có mặt tại ga trước hoặc đúng thời điểm nhóm bắt đầu được phục vụ.
- Đặc điểm: Đây là bài toán tối ưu hóa việc chia dãy số thành các đoạn con, rất phù hợp với Quy hoạch động.
2. Ý tưởng thuật toán
Gọi là thời gian sớm nhất mà người thứ hoàn thành việc mua vé. Để tính , ta xét xem người thứ thuộc nhóm nào. Giả sử nhóm cuối cùng bao gồm các người từ đến (với ).
Khi đó:
- Thời điểm bắt đầu của nhóm này sẽ là: .
- Điều kiện hợp lệ: Vì người thứ là người đến muộn nhất trong nhóm (giả sử danh sách đã sắp xếp theo ), nên để nhóm này hợp lệ thì .
- Thời gian phục vụ của nhóm là tổng của các người từ đến .
- Thời điểm kết thúc .
Ta sẽ lấy giá trị nhỏ nhất có thể của khi thử tất cả các vị trí hợp lệ.
3. Các bước thực hiện
- Sắp xếp: Sắp xếp danh sách người theo thời gian đến tăng dần (nếu đề chưa cho sắp xếp).
- Mảng cộng dồn (Prefix Sum): Tạo mảng để tính nhanh tổng thời gian phục vụ .
- .
- Tổng từ đến là .
- Quy hoạch động:
- Khởi tạo mảng với giá trị vô cùng lớn, .
- Duyệt từ đến .
- Với mỗi , duyệt ngược từ về (đảm bảo ).
- Tính .
- Kiểm tra điều kiện: Nếu , cập nhật:
- Kết quả: Giá trị .
4. Lưu ý khi cài đặt (C++/Python)
- Kiểu dữ liệu: Thời gian có thể lên tới cộng dồn qua nhiều người, nên bắt buộc dùng kiểu số nguyên 64-bit (
long longtrong C++, Python tự động xử lý). - Giới hạn vòng lặp: Vòng lặp trong (duyệt ) chỉ chạy tối đa lần. Độ phức tạp tổng thể là . Với , thuật toán này chạy tốt nếu nhỏ. Nếu lớn xấp xỉ , cần cẩn thận tối ưu hoặc ngôn ngữ chậm như Python có thể bị quá thời gian (TLE).
- Xử lý chỉ số: Lưu ý mảng trong C++ bắt đầu từ 0 hoặc 1 tùy cách bạn cài đặt, hãy đồng bộ chỉ số giữa mảng và mảng quy hoạch động .
Đoạn mã minh họa ý tưởng (C++):
// Giả sử t[] và d[] đã nhập và sắp xếp theo t (1-based index)
// S[] là mảng cộng dồn của d[]
vector<long long> F(N + 1, 2e18); // Khởi tạo giá trị vô cùng lớn
F[0] = 0;
for (int i = 1; i <= N; i++) {
for (int k = 1; k <= C; k++) { // k là số lượng người trong nhóm cuối
int j = i - k;
if (j < 0) break;
long long startTime = max(F[j], t[j+1]);
// Kiểm tra điều kiện: người cuối cùng (i) phải đến trước hoặc đúng lúc bắt đầu
if (t[i] <= startTime) {
long long duration = S[i] - S[j];
F[i] = min(F[i], startTime + duration);
}
}
}
cout << F[N];