Overview

This problem asks us to rearrange and play the tempo values of \(N\) songs to minimize the sum of discomfort scores. If a song whose tempo difference is \(D\) or less has been played in the past, the discomfort score is \(0\). Otherwise, the discomfort score is the difference in tempo between the current song and the immediately preceding song.

Analysis

First, let’s clarify the condition under which the discomfort score becomes \(0\). The discomfort score of the \(j\)-th (\(j \geq 2\)) song becomes \(0\) if “there exists a song among those played in the past whose tempo difference from the current song is \(D\) or less.”

If we sort the tempo values in ascending order, we can say that adjacent elements are “similar” to each other if their difference is \(D\) or less. In the sorted array, we can consider a collection of songs connected by differences of \(D\) or less (connected components) as a single group. Songs within the same group can be treated as similar, mediated by the songs in between, even if their direct difference is not \(D\) or less. Therefore, by playing songs within the same group consecutively, we can make their discomfort scores \(0\).

On the other hand, the tempo difference between different groups is strictly greater than \(D\). When transitioning from one group to another, since all previously played songs are more than \(D\) away from the current song, a discomfort score will always be incurred. In this case, the discomfort score is “the absolute difference from the tempo value of the immediately preceding song.” To minimize the total discomfort, we need to make the difference between the immediately preceding song and the current song during group transitions as small as possible. If we look at the sorted array from left to right, the difference between the maximum value of the previous group and the minimum value of the next group becomes the minimum discomfort during the transition.

Algorithm

1. Sort the tempo array \(A\) in ascending order.
2. Maintain the maximum tempo value in the current group as R, with an initial value of \(A[0]\).
3. Iterate through the array from left to right (for \(i = 1\) to \(N-1\)).
   • If \(A[i] - A[i-1] \leq D\), then \(A[i]\) belongs to the current group, so we update R to \(A[i]\).
   • If \(A[i] - A[i-1] > D\), this indicates a transition to a new group. A discomfort score equal to the difference between the maximum value of the previous group R and the minimum value of the new group \(A[i]\) will be incurred. Therefore, we add \(A[i] - R\) to the total answer, and update R to \(A[i]\).
4. Finally, output the total accumulated discomfort score.

Complexity

• Time Complexity: \(O(N \log N)\) (dominated by sorting)
• Space Complexity: \(O(N)\) (to store the input array)

Implementation Points

By scanning the sorted array just once, we can perform both the grouping and the discomfort score calculation simultaneously. Managing the “maximum value of the current group” with a single variable R allows for a simple and efficient implementation.

Source Code

import sys

def solve():
    input = sys.stdin.readline
    N, D = map(int, input().split())
    A = list(map(int, input().split()))
    A.sort()
    
    ans = 0
    # 現在の連結成分における最大のテンポ値
    R = A[0]
    
    for i in range(1, N):
        if A[i] - A[i - 1] <= D:
            # 同じ連結成分に属する場合、Rを更新
            R = A[i]
        else:
            # 新しい連結成分に移行した場合、直前の成分の最大値との差を足す
            ans += A[i] - R
            R = A[i]
            
    print(ans)

if __name__ == '__main__':
    solve()

This editorial was generated by or-glm5.2-high.