Hướng giải: Phân chia dãy số

Nguồn: CSES

Xây dựng một hàm check(s) nhận vào một giá trị ~s~ và kiểm tra xem có thể chia mảng thành ~k~ mảng con sao cho tổng của mỗi mảng con không vượt quá ~s~ hay không. Hàm duyệt mảng từ trái sang phải và tham lam chọn kích thước lớn nhất có thể cho mỗi mảng con.

Ta có thể giải bài toán một cách hiệu quả bằng cách kết hợp tìm kiếm nhị phân với hàm trên. Ta tìm giá trị lớn nhất ~s~ sao cho không thể chia mảng thành các mảng con thỏa mãn điều kiện. Khi đó, đáp án của bài toán là ~s + 1~.

Thuật toán có độ phức tạp ~O(n.log(M))~, trong đó ~M=10^{18}~ là đáp án lớn nhất có thể.