Overview

A problem where you assign \(N\) packages consecutively by number to \(K\) trucks, and maximize the minimum load capacity among all trucks.

Approach

In this problem, we need to divide the packages into \(K\) groups by partitioning them consecutively by number, with the goal of maximizing the minimum total value (load capacity) among all groups.

A naive approach of trying all possible partitions has too many combinations and is computationally infeasible (for example, \(_{N-1}C_{K-1}\) ways). Also, greedily partitioning from the smallest values doesn’t always lead to the optimal solution.

The key observation is that if we consider the decision problem “For a given value \(x\), can we partition the packages such that every truck has a load capacity of at least \(x\)?”, this can be solved relatively efficiently. And the maximum value of \(x\) for which this decision problem returns YES is exactly the answer we’re looking for.

This technique of “rephrasing a maximization problem as a decision problem and using binary search” is a classic approach, often called “binary search on the answer”.

Specifically: - The upper bound of the answer is approximately the total sum divided by \(K\) (when distributing equally among all trucks) - The lower bound can be set to \(0\) - We use binary search within this range to check “Can we make the minimum load capacity at least \(x\)?”

In the decision function is_possible(x), we greedily make a partition from the front whenever the cumulative sum reaches \(x\) or more. If the final number of partitions is at least \(K\), it’s OK.

Algorithm

1. Set the binary search range: left = 0, right = sum(A) // K + 1
2. Set mid = (left + right) // 2 and evaluate is_possible(mid)
3. If the condition is satisfied, set left = mid; otherwise, set right = mid
4. When right - left == 1, left is the answer

Decision Function is_possible(min_load)

• Add packages sequentially from the front, and make a partition (increment count) whenever the sum reaches min_load or more
• If the number of partitions is at least \(K\), return OK

Complexity

• Time Complexity: \(O(N \log(\sum A_i))\)
  • Each step of binary search performs an \(O(N)\) check
  • The search range is at most around \(\sum A_i\), hence the \(\log\) factor
• Space Complexity: \(O(1)\)
  • No additional data structures are used

Implementation Notes

• In the is_possible function, even if the last remaining group has less than min_load, don’t count it (since there’s no next truck)
• It’s safer to set the initial value of right slightly larger (such as sum(A) // K + 1)
• The decision part can be done by greedily simulating from the front

## Source Code

```python
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:]))

    def is_possible(min_load):
        count = 0
        current_sum = 0
        for a in A:
            current_sum += a
            if current_sum >= min_load:
                count += 1
                current_sum = 0
        return count >= K

    left = 0
    right = sum(A) // K + 1

    while right - left > 1:
        mid = (left + right) // 2
        if is_possible(mid):
            left = mid
        else:
            right = mid

    print(left)

if __name__ == "__main__":
    main()

This editorial was generated by qwen3-coder-480b.