Overview

This problem asks us to rearrange the tempo values of songs to minimize the total “discomfort” caused by sudden changes in tempo (changes where the difference exceeds \(D\)).

Analysis

1. Consider playing the songs sorted in ascending order

First, let’s consider sorting the songs in ascending order of their tempo values and playing them. Let the sorted array of tempo values be \(A'_1, A'_2, \ldots, A'_N\).

When playing in this order, the discomfort score for each song \(A'_j\) (\(j \geq 2\)) is as follows:

• When the difference from the previous song is at most \(D\) (\(A'_j - A'_{j-1} \leq D\)): Since the immediately preceding song acts as a “similar song”, a similar song has already appeared in the past, so the discomfort score is \(0\).
• When the difference from the previous song is greater than \(D\) (\(A'_j - A'_{j-1} > D\)): Since we are playing them in ascending order, all previously played songs have tempos strictly smaller than \(A'_j\) (at most \(A'_{j-1}\)). Thus, the difference between \(A'_j\) and any previously played song is greater than \(D\), meaning no similar song exists. In this case, the discomfort score is the difference from the immediately preceding song, which is \(A'_j - A'_{j-1}\).

In other words, when playing in ascending order, the total discomfort is the sum of the differences between adjacent songs where the tempo difference exceeds \(D\).

2. Why this gives the minimum value (Intuitive understanding)

If we connect songs whose tempo difference is at most \(D\) with edges, they can be divided into several “groups”. Between these groups, there are “gaps” with a width greater than \(D\).

No matter what order we play the songs in, we must eventually play all of them. This means we must travel from the group with the lowest tempos to the group with the highest tempos on the number line.

When moving to a different group (crossing a gap), there will always be a moment when no song from the destination group (or any group with higher tempos) has been played yet. At that moment, a discomfort score of at least the gap’s width is inevitably incurred to cross the gap.

Therefore, the total discomfort cannot be less than the sum of all gap widths. The strategy of sorting and playing in ascending order achieves exactly this minimum discomfort (the sum of the gap widths), making it the optimal playback order.

Algorithm

1. Sort the given array of tempo values \(A\) in ascending order.
2. Initialize a variable ans representing the answer to \(0\).
3. Compute the differences between adjacent elements \(A[i+1] - A[i]\) in order.
4. If the difference is greater than \(D\), add the difference to ans.
5. Print the final value of ans.

Complexity

• Time Complexity: \(O(N \log N)\) Sorting \(N\) elements takes \(O(N \log N)\) time. Since the subsequent loop takes \(O(N)\) time, the overall bottleneck is the sorting, which is well within the time limit.
• Space Complexity: \(O(N)\) We use \(O(N)\) space to store the array \(A\) for the input.

Implementation Points

• Fast I/O: Since \(N\) can be as large as \(10^6\), using sys.stdin.read().split() in Python to read the entire input at once will significantly reduce the execution time.

  Source Code

import sys

def solve():
    # 入力を一括で読み込む
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    N = int(input_data[0])
    D = int(input_data[1])
    A = [int(x) for x in input_data[2:]]
    
    # テンポ値を昇順にソート
    A.sort()
    
    ans = 0
    # 隣接する要素の差が D より大きい場合、その差を足し合わせる
    for i in range(N - 1):
        diff = A[i+1] - A[i]
        if diff > D:
            ans += diff
            
    print(ans)

if __name__ == '__main__':
    solve()

---

This editorial was generated by gemini-3.5-flash-high.