Trên một trục thẳng có n vị trí nguyên (có thể không theo thứ tự) để đặt chuồng. Bác nông dân muốn đặt k con bò vào k trong số n vị trí đó sao cho khoảng cách nhỏ nhất giữa hai con bò bất kỳ là lớn nhất có thể (để chúng không cắn nhau).
Hãy tìm giá trị lớn nhất của khoảng cách nhỏ nhất đó.
Gợi ý: tìm kiếm nhị phân trên đáp án d — kiểm tra bằng thuật toán tham lam xem có thể đặt k con bò sao cho mọi cặp liền kề cách nhau ít nhất d hay không.
Dòng đầu chứa hai số nguyên n và k. Dòng thứ hai chứa n số nguyên là toạ độ các vị trí.
2≤k≤n≤105; 0≤xi≤109; các vị trí đôi một khác nhau.
In ra một số nguyên là khoảng cách nhỏ nhất lớn nhất đạt được.
Ví dụ:
Đầu vào:
5 3
1 2 8 4 9
Đầu ra:
3
Giải thích:
Đang tải editor...