Khoảng Cách Tối Thiểu

Binary-search Buổi 12 — Greedy Algorithm Buổi 13 — Chặt nhị phân đáp án Buổi 16 — Contest Chặng 2
Points
25
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
Uncategorized
Submissions
Đề bài

Trên một đường thẳng có $N$ vị trí đã đặt cọc (đã sắp xếp tăng dần). Cần đặt thêm $K$ cọc mới vào các vị trí đã cho sao cho khoảng cách nhỏ nhất giữa hai cọc liên tiếp bất kỳ (trong số $K$ cọc được chọn) là lớn nhất. In ra khoảng cách lớn nhất đó.

Dữ liệu vào
  • Dòng đầu tiên chứa hai số nguyên $N$ và $K$ $(2 \le K \le N \le 10^5)$.
  • Dòng thứ hai chứa $N$ số nguyên $x_1 < x_2 < \ldots < x_N$ $(0 \le x_i \le 10^9)$.
Dữ liệu ra
  • In ra khoảng cách lớn nhất có thể.
Ví dụ
Input Output
5 3
1 2 4 8 9
3
Giới hạn
  • $2 \le K \le N \le 10^5$
  • $0 \le x_i \le 10^9$
Draft saved