Overview

This is a problem where you distribute \(N\) apples into \(K\) boxes and minimize the total “maximum weight - minimum weight” for each box. It can be solved efficiently by sorting and greedily choosing “where to make the cuts.”

Analysis

Key Insight 1: Sort and Divide into Contiguous Intervals

When placing apples in the same box, it is optimal to select them from contiguous intervals when sorted by weight.

This is because the variance of a box is “maximum value - minimum value,” so selecting non-contiguous values would unnecessarily increase the variance.

Example: When apples have weights \([1, 3, 5, 7]\) - Putting \(\{1, 7\}\) in the same box → variance = \(7 - 1 = 6\) - Putting \(\{1, 3\}\) in the same box → variance = \(3 - 1 = 2\)

Key Insight 2: Think of It as a Partition Problem

Consider this as a problem of dividing a sorted array into \(K\) contiguous intervals.

The variance when putting all apples in one box is \(A[N-1] - A[0]\).

Here, focus on the gaps between adjacent elements: \(gap[i] = A[i+1] - A[i]\).

To divide into \(K\) boxes, we make cuts at \(K-1\) positions. When we cut at position \(i\), the total variance decreases by that \(gap[i]\).

Concrete Example

For \(A = [1, 2, 5, 8, 9]\), \(K = 3\):

• Gaps: \([1, 3, 3, 1]\) (respectively \(2-1, 5-2, 8-5, 9-8\))
• Variance for 1 box: \(9 - 1 = 8\)
• Cut at \(K-1 = 2\) positions → cut at the largest gaps \(3, 3\)
• Result: divide into \([1, 2], [5], [8, 9]\)
• Total variance: \((2-1) + 0 + (9-8) = 1 + 0 + 1 = 2\)
• Calculation: \(8 - 3 - 3 = 2\) ✓

Naive DP Approach

A DP approach where \(dp[i][j]\) = minimum variance when dividing the first \(i\) items into \(j\) boxes would be \(O(N^2 K)\), which causes TLE for \(N = 2 \times 10^5\).

Algorithm

1. Sort the apple weights
2. If \(K \geq N\), each apple can go in a separate box, so the answer is \(0\)
3. Calculate all gaps between adjacent elements: \(gap[i] = A[i+1] - A[i]\)
4. Find the variance for one box: \(total = A[N-1] - A[0]\)
5. Sort gaps in descending order and subtract the top \(K-1\) gaps from \(total\)
6. Output the result

Intuitive understanding: By cutting at large gaps, we can efficiently reduce the variance.

Complexity

• Time complexity: \(O(N \log N)\) (sorting is the bottleneck)
• Space complexity: \(O(N)\) (for storing arrays)

Implementation Notes

• Handle the case \(K \geq N\) specially (answer is \(0\))
• Note that the gap array has \(N-1\) elements
• Sort gaps in descending order and select the top \(K-1\) (or sort in ascending order and keep the lower ones)

Source Code

def solve():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    
    # Sort (it's optimal to put apples with consecutive weights in the same box)
    A.sort()
    
    # dp[i][j] = minimum total variance when dividing the first i apples into j boxes
    # This would be O(N^2 * K), likely causing TLE
    
    # Alternative approach:
    # After sorting, divide N apples into K contiguous intervals
    # The variance of each interval [l, r] is A[r] - A[l]
    # Total variance = sum(A[r_i] - A[l_i]) for each box i
    # 
    # If all apples are in one box: A[N-1] - A[0]
    # Dividing into K boxes means making K-1 cuts
    # Cutting between positions i and i+1 reduces variance by A[i+1] - A[i] (at the boundary between adjacent boxes)
    #
    # More precisely:
    # Looking at the whole picture, the total variance is
    # (sum of maximum values of each box) - (sum of minimum values of each box)
    # 
    # Consider choosing K-1 cut points
    # If cut point is i (0 <= i < N-1), we cut between i and i+1
    # 
    # For one box: A[N-1] - A[0]
    # When cutting at point i, the reduction from that cut is
    # Before cut: ...A[i], A[i+1]... are in the same box
    # After cut: ...A[i] | A[i+1]...
    # 
    # Actually, consider the gap between adjacent elements gap[i] = A[i+1] - A[i],
    # and it's optimal to cut at the K-1 largest gaps
    
    if K >= N:
        # Each apple can go in a separate box (extra boxes are OK)
        print(0)
        return
    
    # Calculate differences between adjacent elements
    gaps = []
    for i in range(N - 1):
        gaps.append(A[i + 1] - A[i])
    
    # Total variance (if all in one box)
    total = A[N - 1] - A[0]
    
    # Choose K-1 cut points = cut at K-1 largest gaps
    # The gaps where we cut are excluded from the variance calculation
    gaps.sort(reverse=True)
    
    # Subtract the K-1 largest gaps
    for i in range(K - 1):
        total -= gaps[i]
    
    print(total)

solve()

---

This editorial was generated by claude4.5opus.