Overview

This is a problem where we divide \(N\) packages among \(K\) trucks as contiguous intervals, and maximize the minimum load among all trucks. “Maximizing the minimum” is classically solved using binary search.

Approach

Key Insight

This problem is in the form “maximize the minimum value.” For such problems, assuming the answer and reducing it to a decision problem is an effective approach.

Specifically, we consider the decision problem: “Can we make all trucks have a load of at least \(X\)?” If we can make this decision, we can find the answer by binary searching on \(X\).

Decision Problem Approach

To determine “whether each truck can have a load of at least \(X\)”, we can use a greedy approach.

1. Load packages onto the current truck from the beginning
2. Once the load becomes at least \(X\), that truck satisfies the condition, so move to the next truck
3. If we can ultimately create \(K\) or more trucks satisfying the condition, it’s OK

Concrete Example

For example, let’s consider whether we can achieve \(X = 5\) with \(A = [3, 2, 4, 1, 5]\) and \(K = 3\).

• Truck 1: \(3 + 2 = 5 \geq 5\) → OK, move to next
• Truck 2: \(4 + 1 = 5 \geq 5\) → OK, move to next
  
• Truck 3: \(5 \geq 5\) → OK

We can divide into 3 trucks, and each truck has at least 5, so it’s achievable.

Binary Search Range

• Lower bound: \(0\) (minimum value is at least 0)
• Upper bound: \(\lfloor \text{total sum} / K \rfloor\) (if larger than this, we can’t divide into \(K\) trucks)

Algorithm

1. Initialize binary search: \(\text{left} = 0\), \(\text{right} = \lfloor \text{total sum} / K \rfloor + 1\)
2. Binary search loop:
   • Calculate \(\text{mid} = (\text{left} + \text{right}) / 2\)
   • Determine “whether each truck can have a load of at least \(\text{mid}\)”
   • If possible, \(\text{left} = \text{mid}\) (we can try larger values)
   • If impossible, \(\text{right} = \text{mid}\) (this value cannot be achieved)
3. Decision function can_achieve_min_load:
   • Greedily load packages from the beginning
   • When the load becomes at least \(\text{min\_load}\), confirm one segment (interval)
   • Return True if the number of confirmed segments is at least \(K\)

Decision flow (when min_load = 5):
Packages: [3, 2, 4, 1, 5]
          ↓
[3,2] → total 5 ≥ 5 → segment 1 confirmed
[4,1] → total 5 ≥ 5 → segment 2 confirmed  
[5]   → total 5 ≥ 5 → segment 3 confirmed
→ 3 segments created, so OK for K=3

Complexity

• Time complexity: \(O(N \log(\text{sum}/K))\)
  • Binary search runs \(O(\log(\text{sum}/K))\) times
  • Each decision scans the array once, so \(O(N)\)
• Space complexity: \(O(N)\)
  • Required to store the input array

Implementation Notes

• In the decision function, we check “whether we can create \(K\) intervals of at least \(X\)” rather than “whether all \(K\) trucks have at least \(X\)”. Even if there’s a remainder in the last interval, we can handle it by including it in the previous interval.
• In binary search, to find “the maximum value satisfying the condition”, we update \(\text{left}\) when the condition is satisfied, and finally output \(\text{left}\) as the answer.

Source Code

def can_achieve_min_load(A, K, min_load):
    """
    Determine whether we can deliver using K or fewer trucks
    such that each truck's load is at least min_load
    """
    truck_count = 1
    current_load = 0
    
    for weight in A:
        current_load += weight
        # If current truck's load becomes at least min_load, move to next truck
        if current_load >= min_load:
            truck_count += 1
            current_load = 0
    
    # Even if the last truck has less than min_load, it's OK if we've used K trucks before
    # truck_count counts as "next truck", so actual trucks used is truck_count-1
    # However, if current_load > 0, the last truck is also being used
    
    # Alternative approach: Can we divide into K trucks?
    # Can we create K segments of at least min_load?
    segments = 0
    current_load = 0
    
    for weight in A:
        current_load += weight
        if current_load >= min_load:
            segments += 1
            current_load = 0
    
    return segments >= K


def solve():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    
    total_sum = sum(A)
    
    # Binary search
    # left: lower bound of achievable minimum value
    # right: upper bound of achievable minimum value
    left = 0
    right = total_sum // K + 1
    
    while right - left > 1:
        mid = (left + right) // 2
        if can_achieve_min_load(A, K, mid):
            left = mid
        else:
            right = mid
    
    print(left)


solve()

---

This editorial was generated by claude4.5opus.