Cắt dây tối đa (Tìm kiếm nhị phân số thực)

Binary-search Buổi 06 — Sắp xếp & Tìm kiếm
Points
46
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
sortsearch
Submissions
Đề bài

Có $N$ sợi dây có độ dài lần lượt là $L_1, L_2, \dots, L_N$. Cần cắt từ $N$ sợi dây này ra đúng $K$ đoạn dây có độ dài bằng nhau (không được nối dây). Hãy dùng tìm kiếm nhị phân trên số thực để tìm độ dài lớn nhất có thể của mỗi đoạn dây, in ra với 6 chữ số thập phân.

Dữ liệu vào

Dòng đầu chứa hai số nguyên dương $N$ và $K$. Dòng thứ hai chứa $N$ số thực $L_1, L_2, \dots, L_N$.

Dữ liệu ra

Một số thực duy nhất làm tròn đến 6 chữ số sau dấu phẩy.

Ví dụ
Input Output
4 11\n8.02 7.43 4.57 5.39 2.005000
2 5\n10 10 4.000000
Giới hạn

$1 \le N \le 10^4$, $1 \le K \le 10^5$, $0 < L_i \le 10^7$.

Draft saved