Phân bổ sách tối ưu (Book Allocation)
Points
65
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
sortsearch
Đề bài
Có $N$ cuốn sách xếp thành một hàng, cuốn thứ $i$ có $P_i$ trang. Cần phân phối tất cả $N$ cuốn sách cho $K$ học sinh sao cho mỗi học sinh nhận một đoạn liên tiếp các cuốn sách (có thể có học sinh không nhận cuốn nào, hoặc mỗi cuốn phải thuộc về đúng một học sinh). Hãy dùng tìm kiếm nhị phân trên đáp án để tìm giá trị nhỏ nhất có thể của tổng số trang nhiều nhất mà một học sinh phải đọc.
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ố nguyên dương $P_1, P_2, \dots, P_N$.
Dữ liệu ra
Một số nguyên duy nhất là tổng số trang lớn nhất nhỏ nhất có thể.
Ví dụ
| Input | Output |
|---|---|
| 4 2\n12 34 67 90 | 113 |
| 3 3\n10 20 30 | 30 |
Giới hạn
$1 \le K \le N \le 10^5$, $1 \le P_i \le 10^9$.
Community Discussion