Overview

Rephrase the problem as sorting the apple weights and then choosing “cut points” between boxes. By cutting at positions where the gap (difference between adjacent weights) is largest, we can minimize the total variation.

Analysis

Key Insight 1: The optimal partition consists of “contiguous intervals after sorting”

Consider the sequence of weights sorted in ascending order. If the apples in a box are non-contiguous in sorted order (e.g., a small and a large apple in the same box, with the middle ones in a different box), the max − min of that box tends to be unnecessarily large.

In fact, if after sorting we have: - Box X contains \(A_i\) and \(A_k\) (\(i<k\)) - Box Y contains \(A_j\) between them (\(i<j<k\))

then Box X’s range is at least \(A_k - A_i\). By adjusting — moving \(A_j\) into Box X, or moving the endpoint elements of Box X into Box Y — we can convert to a “contiguous interval packing” without worsening any box’s range (max − min).
Therefore, we can think of this as the problem of dividing the sorted array into \(K\) contiguous intervals.

Key Insight 2: Each cut reduces the total by exactly the “gap amount”

If we put the entire sorted array \(A\) into one box, the variation is \(A_{N} - A_{1}\) (using 1-indexed notation here).

Now, for example, if we cut between \(A_t\) and \(A_{t+1}\) (insert a boundary there): - Left box’s range: \(A_t - A_1\) - Right box’s range: \(A_N - A_{t+1}\)

The total is: $\((A_t - A_1) + (A_N - A_{t+1}) = (A_N - A_1) - (A_{t+1} - A_t)\)$

In other words, inserting a cut reduces the total by exactly the gap \((A_{t+1} - A_t)\) at that position.

Therefore, to divide into \(K\) boxes we need \(K-1\) cuts, so to minimize the total: - Maximize the total amount reduced (sum of gaps at cut positions) - That is, select the \(K-1\) positions with the largest adjacent differences and cut there

This is optimal.

Why a naive approach is difficult

Exhaustively searching all possible cut positions would result in a combinatorial explosion (e.g., \(N\) can be \(2 \times 10^5\), so this is out of the question), and a straightforward DP could be \(O(NK)\), which is too slow.
Thanks to the observation above, we can reduce it to just selecting the largest gaps, enabling an efficient solution.

Algorithm

1. Sort the array \(A\) in ascending order.
2. Compute the adjacent differences (gaps) \(g_i = A_{i+1} - A_i\) (\(i = 1..N-1\)).
3. Sort the gaps in descending order and let removed be the sum of the top \(K-1\) gaps.
4. The range when all apples are in one box is \((A_N - A_1)\), so the answer is: $\(\text{ans} = (A_N - A_1) - \sum_{i=1}^{K-1} (\text{largest gap}_i)\)$
5. Edge cases:
   • If \(K = N\) (one apple per box), the answer is \(0\).
   • If \(K = 1\), the answer is \(A_N - A_1\).

Concrete Example

\(A = [1, 3, 6, 10],\ K = 2\)
The gaps are \([2, 3, 4]\). The largest \(K-1 = 1\) gap is \(4\).
The total range is \(10 - 1 = 9\), so the answer is \(9 - 4 = 5\).
Indeed, splitting into \([1, 3, 6]\) and \([10]\) gives a total variation of \((6 - 1) + 0 = 5\), which is the minimum.

Complexity

• Time complexity: \(O(N \log N)\) (dominated by sorting: sorting \(A\) and sorting the gaps)
• Space complexity: \(O(N)\) (for the gap array)

Implementation Notes

• When \(K = N\), the answer is always \(0\), so returning early is safe.

• In Python, sorting is fast, so a clean implementation is to sort the gaps in descending order and sum the first \(K-1\) elements.

• Values can be up to \(10^9\), and sums of differences can involve adding up to \(2 \times 10^5\) terms, but Python’s integers (arbitrary precision) handle this without issues.

  Source Code

import sys

def main():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    A.sort()

    if N == 1 or K == N:
        print(0)
        return
    if K == 1:
        print(A[-1] - A[0])
        return

    gaps = [A[i+1] - A[i] for i in range(N - 1)]
    gaps.sort(reverse=True)
    removed = sum(gaps[:K-1])
    ans = (A[-1] - A[0]) - removed
    print(ans)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.