Phân bổ sách tối ưu (Book Allocation)

Binary-search Buổi 06 — Sắp xếp & Tìm kiếm
Points
65
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
sortsearch
Submissions
Đề 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$.

Draft saved