Hướng dẫn giải của [TS10 Lâm Đồng 2025 - 2026] Rô bốt
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.
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ưởng
Mỗi rô bốt là một đoạn ~[X_i-L_i,X_i+L_i]~. Bài toán trở thành chọn nhiều đoạn không giao nhau nhất. Sắp xếp các đoạn theo điểm kết thúc tăng dần, sau đó tham lam chọn đoạn đầu tiên có điểm bắt đầu không nhỏ hơn điểm kết thúc của đoạn vừa chọn.
Độ phức tạp
~O(n \log n)~.
Bình luận