Bài toán yêu cầu tìm giá trị nhỏ nhất của X sao cho có thể chia dãy A thành tối đa K đoạn liên tiếp mà tổng mỗi đoạn không vượt quá X.

Nhận xét quan trọng: Nếu với một giá trị \(X\), ta có thể chia dãy thành \(K\) đoạn, thì với mọi giá trị \(X' > X\), ta cũng chắc chắn có thể chia được (vì các đoạn hiện tại đã thỏa mãn tổng \(\le X < X'\)). Điều này cho thấy tính đơn điệu của hàm kiểm tra, cho phép ta áp dụng phương pháp Chặt nhị phân trên đáp án (Binary Search on Answer).

Chi tiết giải thuật:

1. Xác định khoảng tìm kiếm:
2. Cận dưới (low): Giá trị lớn nhất của một phần tử trong mảng \(A\) (\(\max(A_i)\)), vì mỗi phần tử phải nằm trong một đoạn nào đó.
3. Cận trên (high): Tổng của tất cả các phần tử trong mảng \(A\) (\(\sum A_i\)), trường hợp \(K=1\).
4. Hàm check(mid):
5. Duyệt qua mảng A, cộng dồn các phần tử vào đoạn hiện tại.
6. Nếu tổng vượt quá 'mid', ta bắt đầu một đoạn mới và tăng biến đếm số đoạn lên 1.
7. Nếu sau khi duyệt hết mảng, số đoạn \(\le K\) thì giá trị 'mid' là khả thi.
8. Chặt nhị phân:
9. Nếu check(mid) trả về true, ta ghi nhận đáp án và thử tìm giá trị nhỏ hơn (high = mid - 1).
10. Nếu check(mid) trả về false, ta cần tăng giới hạn X (low = mid + 1).

Độ phức tạp thời gian: \(O(N \log(\sum A))\), trong đó \(N\) là số lượng phần tử và \(\sum A\) là tổng các phần tử. Với \(N=10^5\) và \(\sum A \approx 10^{14}\), \(\log(\sum A) \approx 47\), tổng số phép tính khoảng \(4.7 \times 10^6\), hoàn toàn đáp ứng thời gian chạy 1s.