Phủ sóng các thành phố trọng điểm
Points
55
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
Uncategorized
Đề bài
Trên một tuyến đường cao tốc thẳng có $N$ thành phố. Thành phố thứ $i$ ở tọa độ $x_i$ và có độ trễ cho phép nghịch đảo bởi trọng số $w_i$. Nếu đặt một trạm phát sóng tại tọa độ $p$, chi phí trễ tại thành phố $i$ là $w_i \cdot |x_i - p|$. Bạn có tối đa $K$ trạm phát sóng được đặt tại bất kỳ tọa độ thực nào trên tuyến đường. Hãy tìm giá trị chi phí trễ lớn nhất nhỏ nhất có thể ($\min \max_{i} (w_i \cdot \min_j |x_i - p_j|)$). In kết quả làm tròn đến 4 chữ số thập phân.
Dữ liệu vào
Dòng đầu chứa hai số nguyên $N, K$. $N$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $x_i$ và $w_i$.
Dữ liệu ra
Một số thực duy nhất làm tròn đến 4 chữ số thập phân.
Ví dụ
| Input | Output |
|---|---|
| 3 1 0 1 10 1 5 2 |
5.0000 |
| 4 2 0 1 2 1 10 2 12 2 |
2.0000 |
Giới hạn
- $1 \le K \le N \le 10^4$
- $-10^6 \le x_i \le 10^6$, $1 \le w_i \le 1000$
Community Discussion