Nhảy đá qua sông

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

Một dòng sông có chiều rộng $L$, bờ bên này ở tọa độ $0$ và bờ bên kia ở tọa độ $L$. Giữa sông có $N$ hòn đá nằm tại các tọa độ $d_1 < d_2 < \dots < d_N$ ($0 < d_i < L$). Một chú ếch muốn nhảy từ bờ $0$ sang bờ $L$ bằng cách nhảy qua các hòn đá.

Để thử thách chú ếch, người ta được phép bỏ đi tối đa $M$ hòn đá (không thể bỏ hai bờ $0$ và $L$). Hãy tìm độ dài bước nhảy ngắn nhất lớn nhất có thể mà chú ếch phải thực hiện để đi từ $0$ đến $L$.

Dữ liệu vào
  • Dòng đầu tiên chứa ba số nguyên $L, N, M$.
  • Dòng thứ hai chứa $N$ số nguyên $d_1, d_2, \dots, d_N$.
Dữ liệu ra

In ra độ dài bước nhảy ngắn nhất lớn nhất có thể.

Ví dụ
Input Output
25 5 2

2 11 14 17 21 | 4 | | 10 2 0 3 7 | 3 |

Giới hạn
  • $1 \le L \le 10^9$
  • $0 \le M \le N \le 10^5$
  • $0 < d_1 < d_2 < \dots < d_N < L$.
Draft saved