💻
Elearning
CodePath
Problems
Contests
Roadmap
🔐 Login
Trạm nghỉ bắt buộc
restfee
Trên một tuyến đường có N vị trí có thể xây trạm nghỉ, tọa độ là a1, a2, ..., aN. Cần giữ lại đúng M vị trí để xây trạm, trong đó vị trí nhỏ nhất và lớn nhất bắt buộc phải được giữ lại. Hãy tối đa hóa khoảng cách nhỏ nhất giữa hai trạm nghỉ liên tiếp sau khi chọn. **Yêu cầu:** Viết chương trình giải bài toán trên. **Dữ liệu vào:** Vào từ file `BAI5.INP` gồm: - Dòng 1 chứa N và M. - Dòng 2 chứa N số nguyên a1, a2, ..., aN. **Kết quả:** Ghi ra file `BAI5.OUT` gồm: - Một số nguyên duy nhất là giá trị lớn nhất của khoảng cách nhỏ nhất. **Ràng buộc:** - $2 ≤ M ≤ N ≤ 10^5$ - $|ai| ≤ 10^9$ - Các tọa độ đôi một khác nhau **Ví dụ 1** | Input | Output | Giải thích | |---|---|---| | 5 3<br> 10 -5 3 -2 1| 7 | Sắp xếp: -5 -2 1 3 10. Bắt buộc giữ -5 và 10, chọn thêm 3 thì khoảng cách nhỏ nhất là min(8,7)=7, là lớn nhất. | **Phân chia subtask:** - Subtask 1 (20% số điểm): $N ≤ 20.$ - Subtask 2 (30% số điểm): $N ≤ 2000.$ - Subtask 3 (50% số điểm): $N ≤ 10^5.$
✅ Đã AC: 0 / 0 submissions
⬅ Contest
🚀 Nộp bài
💡 Gợi ý AI
📌 Bài kế
📋 Copy đề
⚙️
⬅ Contest
🚀 Nộp bài
💡 Gợi ý
📌 Bài kế
📋 Copy
📖 Hướng dẫn học tập
Học trò tri ân
☕ Một ly cà phê sẻ chia
Bạn bè ủng hộ
🍜 Một bát phở ấm lòng
💳 Quét mã ủng hộ tuỳ tâm nhé!
💬 Liên hệ Zalo!
Đóng