Overview

This is a problem where you divide \(N\) packages in order (as consecutive intervals) among \(K\) trucks, and maximize the “minimum” total load among all trucks.

Analysis

The keyword “maximize the minimum”

In competitive programming, problems that ask to “maximize the minimum” or “minimize the maximum” are extremely well-suited for binary search.

Let’s consider the decision problem: “Can we make the minimum value at least \(X\)?” If \(X\) is too large, no valid partition exists; conversely, if \(X\) is small enough, it becomes easy to achieve. Since the result has monotonicity (there exists a threshold value where the answer switches from possible to impossible), we can efficiently find the optimal \(X\) using binary search.

Decision problem: Can we make the minimum load at least \(X\)?

This decision can be solved using a greedy algorithm.

1. Look at the packages starting from the first one, and keep adding packages to the current truck until its total load becomes at least \(X\).
2. The moment the total reaches \(X\) or more, finalize that truck’s packages and move on to the next truck.
3. Repeat this procedure. If we can ultimately create \(K\) or more intervals (trucks), then we judge that making the minimum at least \(X\) is “possible.”

※ If we can create \(K\) or more intervals, we can simply include all remaining packages in the last truck. Since that truck’s load will still be at least \(X\), there is no problem.

Algorithm

1. Set the range for binary search
   • Set the lower bound low to \(1\) and the upper bound high to the total weight of all packages (\(\sum A_i\)).
2. Perform binary search
   • Calculate the midpoint \(mid = (low + high) // 2\).
   • Use the greedy algorithm to determine: “Can we make every truck’s load at least \(mid\)?”
   • If possible: An even larger value might be achievable, so update the answer to \(mid\) and continue searching with low = mid + 1.
   • If impossible: \(mid\) is too large, so reduce the search range with high = mid - 1.
3. Output the final answer
   • The value of ans when the search finishes is the maximum achievable minimum value.

Complexity

• Time complexity: \(O(N \log(\sum A_i))\)
  • The number of binary search iterations is \(O(\log S)\), where \(S\) is the total weight of the packages.
  • Each search step’s decision (greedy algorithm) takes \(O(N)\).
  • For \(N=10^5, \sum A_i \approx 10^{14}\), \(\log(\sum A_i)\) is slightly under \(50\), which comfortably fits within the time limit.
• Space complexity: \(O(N)\)
  • Depends on the size of the list storing the package weights.

Implementation Notes

• Fast I/O: In Python, since the number of packages \(N\) can be as large as \(10^5\), using sys.stdin.read().split() to read all input at once can reduce execution time.

• Binary search boundaries: Be careful not to make mistakes in the update conditions for low and high.

• Early termination in the decision function: Within the greedy algorithm’s loop, returning True as soon as the number of intervals reaches \(K\) can provide a slight speedup.

  Source Code

import sys

def solve():
    # 標準入力から全てのデータを読み込み、空白で分割してリストにする
    # 大量の入力データを高速に処理するための手法です
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # N: 荷物の個数, K: トラックの台数
    N = int(input_data[0])
    K = int(input_data[1])
    # A: 各荷物の重さのリスト
    A = list(map(int, input_data[2:]))
    
    # 二分探索の範囲を設定
    # 各トラックの積載量の最小値として達成可能な最大値を探索します
    # 最小値の下限は1（各荷物の重さが1以上のため）、上限は全ての荷物の重さの合計をKで割った値です
    low = 1
    high = sum(A) // K
    ans = 1
    
    # 二分探索のメインループ
    while low <= high:
        mid = (low + high) // 2
        
        # midが0の場合は、最小値を1として扱う（制約上ansは1以上になるため）
        if mid == 0:
            low = 1
            continue
        
        # 判定問題: 全てのトラックの積載量をmid以上にできるか？
        # 欲張り法を用いて、重さの合計がmid以上になるように荷物を区切っていき、
        # K個以上の区間が作れるかを確認します。
        count = 0
        current_sum = 0
        possible = False
        
        for weight in A:
            current_sum += weight
            if current_sum >= mid:
                count += 1
                current_sum = 0
                # すでにK個以上の区間が見つかった場合は、残りの荷物を最後のトラックに
                # 含めることができるため、このmidは達成可能と判断してループを抜けます。
                if count >= K:
                    possible = True
                    break
        
        if possible:
            # mid以上の積載量を確保できる場合、より大きな値を試みる
            ans = mid
            low = mid + 1
        else:
            # mid以上の積載量を確保できない場合、より小さな値を試みる
            high = mid - 1
            
    # 結果を出力
    sys.stdout.write(str(ans) + '\n')

if __name__ == '__main__':
    solve()

This editorial was generated by gemini-3-flash-preview.