Overview

This is a problem where we cut a log at \(K\) points to divide it into \(K+1\) fragments, and we want to minimize the maximum fragment length \(M\).

Approach

If we try to solve the problem directly, we would need to consider combinations of choosing \(K\) points from \(N-1\) possible positions, resulting in extremely large computational complexity. Instead, we use binary search to transform the problem into a decision problem: “Can we make the maximum value \(M\) at most \(X\)?” If \(X\) is too large, fewer cuts are needed; if \(X\) is too small, many cuts are required. We exploit this monotonic property to find the minimum \(X\) that satisfies the condition using binary search.

Algorithm

1. Set the binary search range. The left bound \(left\) is the maximum length of a single piece (since a single piece cannot be further divided), and the right bound \(right\) is the sum of all piece lengths.
2. At each step, compute \(mid = (left + right) // 2\) and determine whether the maximum fragment length can be made at most \(mid\).
3. Decision method: Iterate through the pieces from left to right, accumulating their lengths. When the total exceeds \(mid\), make a cut and increment the cut count. If the final number of cuts is at most \(K\) (i.e., the number of fragments is at most \(K+1\)), then \(mid\) is achievable.
4. If achievable, set \(right = mid\); otherwise, set \(left = mid + 1\). Narrow the search range and repeat until \(left = right\).

Complexity

• Time complexity: \(O(N \log(\sum A_i))\)
  • The number of binary search iterations is \(O(\log(\sum A_i))\)
  • Each decision check runs in \(O(N)\)
• Space complexity: \(O(N)\)
  • For storing the input array

Implementation Notes

• Input is read all at once using sys.stdin.read for faster I/O.

• The binary search termination condition is left < right, and the final answer is left.

• Important note during the decision check: Since the last fragment must also be counted, count += 1 is needed after the loop.

• Relationship between cuts and fragments: \(K\) cuts produce \(K+1\) fragments, so the decision condition is count <= k + 1.

  Source Code

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    n = int(data[0])
    k = int(data[1])
    A = list(map(int, data[2:2+n]))
    
    left = max(A)
    right = sum(A)
    
    while left < right:
        mid = (left + right) // 2
        count = 0
        current = 0
        for a in A:
            if current + a > mid:
                count += 1
                current = a
            else:
                current += a
        count += 1
        
        if count <= k + 1:
            right = mid
        else:
            left = mid + 1
            
    print(left)

if __name__ == "__main__":
    main()

This editorial was generated by deepseekv3.