Overview

This is a problem where we divide \(N\) apples into \(K\) groups (boxes) and minimize the total sum of “difference between maximum and minimum” for each group.

Analysis

1. Think by sorting the apples

Intuitively, placing apples with similar weights into the same box should result in a smaller “variation.” In fact, when apples are sorted in ascending order by weight, it is optimal to assign each box a contiguous range in the sorted array.

If the assignment is not contiguous (i.e., skipping some apples), we can include the skipped apples into one of the adjacent boxes without increasing the variation, thereby consolidating the boxes.

2. Formulating mathematically

Let the sorted apples be \(A'_1, A'_2, \ldots, A'_N\). We divide these into \(K\) contiguous intervals. For example, the first box covers \(A'_1\) to \(A'_{i_1}\), the second box covers \(A'_{i_1+1}\) to \(A'_{i_2}\), and so on.

The total variation across all boxes is: \((A'_{i_1} - A'_1) + (A'_{i_2} - A'_{i_1+1}) + \dots + (A'_N - A'_{i_{K-1}+1})\)

Let’s rearrange this expression. Define the difference between adjacent elements as \(D_i = A'_{i+1} - A'_i\). The total range (difference between maximum and minimum) is \(\sum_{i=1}^{N-1} D_i = A'_N - A'_1\). The above total can be viewed as “the sum of all differences” minus “the differences at the positions chosen as box boundaries.”

3. Choosing optimal boundaries

To divide \(N\) elements into \(K\) intervals, we need to choose \(K-1\) “boundaries” from the \(N-1\) gaps between adjacent elements.

To minimize the total, we should select the \(K-1\) largest gaps as boundaries and exclude them. In other words, we sum up the \(N-K\) smallest gaps to obtain the minimum total variation.

Algorithm

1. Sort the apple weights \(A\) in ascending order.
2. Compute all adjacent differences \(D_i = A_{i+1} - A_i\) to form the array \(D\) (which has \(N-1\) elements).
3. Sort the difference array \(D\) in ascending order.
4. Compute and output the sum of the smallest \(N-K\) elements of \(D\).
   • When \(K=1\), all differences are summed (equal to \(A_N - A_1\)).
   • When \(K=N\), nothing is summed (the result is \(0\)).

Complexity

• Time complexity: \(O(N \log N)\)
  • Sorting the apple weights takes \(O(N \log N)\).
  • Computing the differences takes \(O(N)\), and sorting the difference array takes \(O(N \log N)\).
• Space complexity: \(O(N)\)
  • \(O(N)\) memory is needed to store the input data and the difference array.

Implementation Notes

• Even for edge cases such as \(K=1\) or \(K=N\), this algorithm (selecting the smallest \(N-K\) values) works correctly.

• Since \(N\) and \(A_i\) can be large, in Python it is faster to read all input at once using sys.stdin.read().split().

  Source Code

import sys

def solve():
    # Read all input data at once for efficient processing
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    n = int(input_data[0])
    k = int(input_data[1])
    a = list(map(int, input_data[2:]))
    
    # If the number of boxes is at least the number of apples,
    # each box can contain a single apple, resulting in a variability of 0.
    if k >= n:
        print(0)
        return
    
    # Sorting the apple weights allows us to group them into contiguous segments.
    # The sum of variabilities for K boxes is equivalent to the total range
    # (max(A) - min(A)) minus the (K-1) largest gaps between adjacent elements.
    a.sort()
    
    # Calculate the differences between adjacent apples in the sorted list.
    diffs = [a[i+1] - a[i] for i in range(n - 1)]
    
    # Sorting the differences to easily pick the smallest or largest ones.
    diffs.sort()
    
    # To minimize the sum of variabilities, we keep the (n-k) smallest differences
    # within the boxes and treat the (k-1) largest differences as boundaries between boxes.
    print(sum(diffs[:n-k]))

if __name__ == '__main__':
    solve()

---

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