Editorial for Đèn Lồng Phố Cổ


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: Nghaiz

Lời giải: Đèn Lồng Phố Cổ

Chủ đề: vòng lặp for, list, sắp xếp

Tóm tắt đề

Con đường là đoạn \([0, L]\), có \(n\) đèn ở các vị trí \(x_i\). Mỗi đèn chiếu sáng \([x_i - d, x_i + d]\). Tìm \(d\) nhỏ nhất để cả con đường được chiếu sáng.

Ý tưởng

Bước 1: sắp xếp. Sau khi sắp xếp các vị trí đèn tăng dần \(x_1 \leq x_2 \leq \dots \leq x_n\), con đường được chia thành ba loại "đoạn tối":

  1. Đầu đường: đoạn \([0, x_1]\). Chỉ có đèn thứ nhất chiếu tới được điểm \(0\), nên cần \(d \geq x_1\).
  2. Cuối đường: đoạn \([x_n, L]\). Tương tự, cần \(d \geq L - x_n\).
  3. Giữa hai đèn liên tiếp: đoạn \([x_i, x_{i+1}]\). Đèn bên trái chiếu sang phải, đèn bên phải chiếu sang trái, hai vùng sáng gặp nhau ở chính giữa. Vậy cần \(d \geq \dfrac{x_{i+1} - x_i}{2}\).

Bước 2: lấy giá trị lớn nhất trong tất cả các yêu cầu trên bằng một vòng for:

\(d = \max\left(x_1,\; L - x_n,\; \max_i \dfrac{x_{i+1} - x_i}{2}\right)\)

Lưu ý đáp án có thể là số lẻ \(.5\) (ví dụ đèn ở \(0\) và \(7\) thì \(d = 3.5\)). Phải dùng phép chia / chứ không dùng //.

Độ phức tạp

Sắp xếp \(O(n \log n)\), duyệt \(O(n)\).

Code mẫu

n, l = map(int, input().split())
xs = sorted(map(int, input().split()))

d = max(xs[0], l - xs[-1])                  # đầu đường và cuối đường
for i in range(1, n):
    d = max(d, (xs[i] - xs[i - 1]) / 2)     # khoảng trống giữa hai đèn

print(f"{d:.10f}")

Comments

There are no comments at the moment.