Tutorial — Khoảng Phủ

Sắp xếp mảng $a$ theo thứ tự tăng dần. Khi đó, một giá trị đại diện sẽ chịu trách nhiệm phủ một đoạn phần tử liên tiếp $[a_L, a_R]$ sao cho hiệu $a_R - a_L$ nhỏ hơn hoặc bằng $2D$.

Nếu một giá trị $D$ cho phép phủ toàn bộ mảng với không quá $k$ đoạn, thì mọi giá trị lớn hơn $D$ cũng đều thỏa mãn. Do đó, bài toán có tính chất đơn điệu đối với khoảng cách $D$.

Sử dụng tìm kiếm nhị phân để tìm giá trị $D$ nhỏ nhất trong khoảng $[0, 10^9]$. Với mỗi giá trị $D$ thử nghiệm, kiểm tra tính khả thi bằng thuật toán tham ăn chọn đoạn dài nhất có thể bắt đầu từ phần tử chưa được phủ nhỏ nhất.