THHV 2025 - DX03 - 11 - Những chú bò hung dữ
Xem dạng PDFTrong trường hợp đề bài hiển thị không chính xác, bạn có thể tải đề bài tại đây: Đề bài
An được nhận vào làm việc trong một trang trại lớn với nhiệm vụ chăn dắt đàn bò. Vì muốn tiết kiệm công sức, An đã đóng ~N~ cái cọc dọc theo một con đường thẳng tại các vị trí có tọa độ lần lượt là ~x_1, x_2, \dots, x_N~, sau đó buộc bò vào các cọc này để không lo chúng chạy mất.
Chủ trang trại giao cho An chăm dọc ~C~ con bò. Tuy nhiên những con bò này không thích đứng gần nhau, nếu bị buộc quá gần nhau chúng sẽ trở nên khó kiểm soát và hung dữ.
Để tránh các con bò xảy ra xung đột, An muốn buộc mỗi con vào một cái cọc sao cho khoảng cách nhỏ nhất giữa hai con bò bất kì là lớn nhất có thể, biết rằng khoảng cách giữa hai con bò ~i~ và ~j~ bằng ~|x_i - x_j|~?
Yêu cầu: Tìm giá trị lớn nhất này.
Input
Dòng đầu ghi ~N, C~ ~(2 \le C \le N \le 10^5)~
~N~ dòng tiếp theo mỗi dòng chứa số nguyên ~x_i~ ~(0 \le x_i \le 10^9)~ thể hiện vị trí của mỗi cọc. Không có hai cọc nào cùng vị trí.
Output
In ra một số nguyên là giá trị lớn nhất của khoảng cách nhỏ nhất giữa hai con bò bất kì
Scoring
| Subtask | Điểm | Ràng buộc |
|---|---|---|
| 1 | ~20\%~ | ~C = 2~ |
| 2 | ~20\%~ | ~C = 3~ |
| 2 | ~30\%~ | ~N, C \le 50, x[i] \le 1000~ |
| 3 | ~30\%~ | Không có ràng buộc gì |
Sample Input 1
5 3
1
2
8
4
9
Sample Output 1
3
Bình luận
admin ơi sao mà ko chấm dc bài vậy,mong ad sửa lỗi này em cảm ơn!
h thì chạy dc rồi!