Một đội quân cần bố trí các đơn vị phòng thủ dọc theo một con đường thẳng. Vị trí của điểm yếu trên con đường được cho trước. Mỗi đơn vị phòng thủ khi đặt tại một điểm yếu có thể bảo vệ tất cả các điểm yếu khác trong phạm vi bán kính tính từ (tức là bảo vệ các điểm trong đoạn ).
Yêu cầu: Hãy tìm số lượng đơn vị phòng thủ ít nhất cần đặt để bảo vệ tất cả điểm yếu.
Dữ liệu:
Gồm nhiều bộ test.
Mỗi bộ test gồm hai dòng:
Dòng đầu tiên chứa hai số nguyên và .
Dòng thứ hai chứa số nguyên là vị trí của các điểm yếu.
Dữ liệu kết thúc bằng một dòng chứa "-1 -1".
Kết quả: Với mỗi bộ test, in ra một số nguyên duy nhất là số đơn vị phòng thủ tối thiểu cần dùng.
Đặt một đơn vị tại điểm 7, nó sẽ bảo vệ các điểm trong [-3, 17], tức là các điểm {1, 7, 15}.
Điểm yếu tiếp theo chưa được bảo vệ là 20. Đặt một đơn vị tại 25, nó sẽ bảo vệ [15, 35], tức là các điểm {15, 20, 21, 25, 30}.
Tất cả các điểm đã được bảo vệ. (Thực ra, chiến lược tốt hơn là đặt tại 15, sẽ bao phủ [5, 25]).
Một cách tối ưu: Đặt tại 7 (che 1,7); đặt tại 20 (che 15,20,21,25,30). Vẫn cần 3 đơn vị.
Cách tối ưu nhất: Sắp xếp các điểm: 1, 7, 15, 20, 21, 25, 30.
Điểm đầu tiên là 1. Ta cần đặt 1 đơn vị. Ta đặt nó càng xa về bên phải càng tốt mà vẫn che được điểm 1. Điểm xa nhất trong tầm của 1 là 7. Ta đặt đơn vị tại 7. Nó che được các điểm trong đoạn [7-10, 7+10] = [-3, 17], tức là các điểm {1, 7, 15}.
Điểm tiếp theo chưa được che là 20. Điểm xa nhất trong tầm của 20 là 30. Đặt đơn vị tại 30. Nó che được [20, 40], tức là {20, 21, 25, 30}.
Tất cả các điểm đã được che. Ta cần 2 đơn vị. (Ví dụ trên trang gốc POJ cho ra 3, có thể đề bài yêu cầu đặt đơn vị tại chính điểm yếu). Nếu đặt tại điểm yếu: đặt tại 7 che 1,7; đặt tại 21 che 15,20,21,25; đặt tại 30 che 30. Tổng cộng 3 đơn vị.
