Ý tưởng

Chặt nhị phân đáp án trong đoạn từ ~\max(a_i)~ đến ~\sum a_i~. Với một giá trị ~X~, kiểm tra bằng tham lam: duyệt từ trái sang phải, gom nhiều chương nhất có thể vào tập hiện tại sao cho tổng không vượt quá ~X~; nếu số tập cần dùng không quá ~k~ thì ~X~ khả thi.

Độ phức tạp

~O(n\log \sum a_i)~.