Hướng dẫn giải của Bessie Giảm Tốc

Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Tác giả: huunguyen

Lời giải: Bessie Giảm Tốc

Hướng tiếp cận

Mô phỏng quá trình di chuyển của Bessie, xử lý các sự kiện giảm tốc theo thứ tự thời gian thực tế xảy ra.

Nhận xét quan trọng

Có hai loại sự kiện: xảy ra tại thời điểm cố định (T) và xảy ra tại khoảng cách cố định (D).
Sự kiện kiểu T giữ nguyên thứ tự thời gian; sự kiện kiểu D cũng vậy theo khoảng cách.
Tại mỗi bước, chỉ cần so sánh sự kiện T nhỏ nhất chưa xử lý với sự kiện D nhỏ nhất chưa xử lý để biết sự kiện nào xảy ra tiếp theo.
Khi có cả T và D xảy ra cùng lúc, D được xử lý trước.

Thuật toán

Đưa các sự kiện T và D vào hai hàng đợi ưu tiên (min-heap).
Theo dõi trạng thái: vị trí hiện tại curDist, thời gian hiện tại curTime, tốc độ hiện tại $\frac{1}{speedVal}$ .
Tại mỗi bước:
- Tính thời gian xảy ra của sự kiện T đầu tiên và D đầu tiên.
- Nếu không còn sự kiện nào trước khi kết thúc, tính thời gian về đích.
- Ngược lại, tiến đến sự kiện gần nhất, cập nhật vị trí/thời gian, tăng speedVal.
Làm tròn kết quả đến giây gần nhất.

Độ phức tạp

Thời gian: $O (N \log N)$
Bộ nhớ: $O (N)$

Bình luận

Không có bình luận tại thời điểm này.