Overview

A problem where \(N\) apples are distributed into \(K\) boxes, and we want to minimize the total “difference between the maximum and minimum weight” of each box.

Analysis

The key insight of this problem is that putting apples with similar weights into the same box minimizes the total variation across all boxes. Therefore, we first sort the apples in ascending order of weight. By sorting, we can suppress variation by placing adjacent apples into the same box.

Next, consider dividing \(N\) apples into \(K\) groups (boxes). This corresponds to partitioning the sorted sequence of apples into \(K\) contiguous intervals.

Here is an important observation: - The variation of each box is “maximum value - minimum value” within that box. - When creating groups by partitioning the sorted sequence, the variation of each interval is the difference between its endpoints. - In other words, the cost depends on where we choose not to split (= where we keep elements connected) relative to the total sum of adjacent differences.

Therefore, we should remove the \(K-1\) largest differences from the total sum of adjacent differences. By removing these differences, we create splits at those positions, and those costs are not added.

For example: - If the apple weights are [1, 3, 5, 7, 9] and the number of boxes is \(K = 3\), - The adjacent differences are [2, 2, 2, 2], with a total of \(8\) - Selecting the largest \(K-1 = 2\) differences to skip gives a cost of \(8 - 2 - 2 = 4\)

In this way, the optimal solution is obtained by the approach: sort and compute differences → remove the \(K-1\) largest ones.

Algorithm

1. Sort the list of apple weights \(A\) in ascending order.
2. Compute the differences between adjacent elements and store them in a list diff (of length \(N-1\)).
3. Sort diff in descending order.
4. The answer is the total sum of diff minus the sum of the top \(K-1\) elements.

※ Prefix sums are used to efficiently compute the sums.

Complexity

• Time complexity: \(O(N \log N)\) (dominated by sorting)
• Space complexity: \(O(N)\)

Implementation Notes

• Since apple weights can be up to \(10^9\), differences may not fit in 32-bit integers, so using a language with arbitrary precision integers like Python is safe.

• sys.stdin.read is used for fast input reading.

• itertools.accumulate is used to precompute prefix sums, making sum calculations efficient.

• When \(K = 1\), there are no elements to skip, so special handling is needed.

  Source Code

import sys
from itertools import accumulate

def main():
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    K = int(data[1])
    A = list(map(int, data[2:]))
    
    A.sort()
    
    # 隣接するりんごの重さの差を計算
    diff = [A[i+1] - A[i] for i in range(N-1)]
    
    # 差を降順にソートして、大きい方からK-1個を選ばない（つまり、K-1個のギャップを無視）
    diff.sort(reverse=True)
    
    # 累積和を使って高速に計算
    cumsum = [0] + list(accumulate(diff))
    
    # 全体の差の合計から、選ばないK-1個の差の合計を引く
    total_diff = cumsum[-1]
    skip_sum = sum(diff[:K-1]) if K > 1 else 0
    
    result = total_diff - skip_sum
    print(result)

if __name__ == "__main__":
    main()

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