Đặt bò vào chuồng

Binary-search Buổi 13 — Chặt nhị phân đáp án greedy sorting
Points
15
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
sortsearch
Submissions
Đề bài

Trang trại có $N$ chuồng bò nằm dọc theo một đường thẳng tại các tọa độ $x_1, x_2, \dots, x_N$. Người nông dân có $K$ con bò và muốn xếp mỗi con vào một chuồng khác nhau sao cho khoảng cách nhỏ nhất giữa hai con bò bất kỳ là lớn nhất có thể.

Dữ liệu vào
  • Dòng đầu tiên chứa hai số nguyên $N$ và $K$.
  • Dòng thứ hai chứa $N$ số nguyên $x_1, x_2, \dots, x_N$.
Dữ liệu ra

In ra khoảng cách nhỏ nhất lớn nhất có thể đạt được.

Ví dụ
Input Output
5 3

1 2 8 4 9 | 3 | | 4 2 10 2 5 20 | 18 |

Giới hạn
  • $2 \le K \le N \le 10^5$
  • $0 \le x_i \le 10^9$ (các $x_i$ đôi một phân biệt).
Draft saved