Chặt Nhị Phân Theo Kết Quả: Chia Gỗ Tối Ưu

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

Có N thanh gỗ, thanh thứ i có độ dài A[i]. Bạn cần cắt các thanh gỗ này thành ít nhất K đoạn bằng nhau, mỗi đoạn có độ dài nguyên dương L (phần thừa không đủ L của mỗi thanh sẽ bỏ đi). Hãy tìm độ dài nguyên L lớn nhất có thể cắt được ít nhất K đoạn.

Dữ liệu vào (Input)
  • Dòng 1: Hai số nguyên dương N và K (1 ≤ N ≤ 10^5, 1 ≤ K ≤ 10^9).
  • Dòng 2: N số nguyên dương A[1], A[2], ..., A[N] (1 ≤ A[i] ≤ 10^9).
Dữ liệu ra (Output)
  • In ra độ dài nguyên lớn nhất L (nếu không thể cắt được K đoạn độ dài ≥ 1, in 0).
Ví dụ mẫu
Sample Input 1
4 11
802 743 457 539
Sample Output 1
200
Sample Input 2
3 6
10 15 20
Sample Output 2
6
Draft saved