Overview

This problem asks us to rearrange the tempo values \(A_i\) of \(N\) given songs to minimize the “total discomfort” caused by the tempo differences between adjacent songs or previously played songs.

Analysis

The key to solving this problem is to view the tempo values as points on a number line and group similar songs together (as connected components).

1. The “Similar” Relationship and Grouping

Two songs with a tempo difference of \(D\) or less are defined as “similar”. Let \(A\) be the array of tempo values sorted in ascending order. If we connect adjacent elements with a line when their difference is \(D\) or less, we can divide them into several groups.

For example, let’s consider the case where \(D = 2\) and the tempo values are \(A = [1, 3, 10, 11]\). - The difference between \(1\) and \(3\) is \(2 \le D\), so they belong to the same group. - The difference between \(3\) and \(10\) is \(7 > D\), so they belong to different groups. - The difference between \(10\) and \(11\) is \(1 \le D\), so they belong to the same group.

As a result, they are divided into two groups: \(\{1, 3\}\) and \(\{10, 11\}\).

2. Playback Order Within a Group

If songs belonging to the same group are played consecutively in ascending (or descending) order of their tempos, then from the second song onwards, the difference with the immediately preceding song will always be \(D\) or less. Therefore, within the same group, it is possible to play all songs while keeping the discomfort score at \(0\).

3. Transitioning Between Groups

The issue arises when transitioning to a different group (e.g., moving from the \(\{1, 3\}\) group to the \(\{10, 11\}\) group). When playing the first song of a new group, since no song “similar” to it (difference of \(D\) or less) has been played in the past, a discomfort score will inevitably be incurred.

The discomfort score at this point is the “tempo difference with the immediately preceding song”. To minimize this difference, it is optimal to transition from the maximum value (right end) of the previous group to the minimum value (left end) of the next group. In the above example, playing \(10\) immediately after playing \(3\) minimizes the tempo difference, resulting in a discomfort score of \(10 - 3 = 7\).

Conclusion

It is optimal to play all songs in ascending order of their tempo values (the sorted order). In this case, a discomfort score is incurred only at the boundaries where “the tempo difference between adjacent songs in the sorted array is greater than \(D\)”. The discomfort score at such a boundary is simply the tempo difference between the adjacent songs (\(A_{i+1} - A_i\)).

Therefore, the minimum value we seek is the “sum of the differences at positions where the difference between adjacent elements is greater than \(D\)” in the sorted array.

Algorithm

1. Sort the given array of tempo values \(A\) in ascending order.
2. Initialize a variable ans to \(0\) to keep track of the total discomfort.
3. Loop from \(i = 0\) to \(N-2\) and calculate the difference between adjacent elements: diff = A[i+1] - A[i].
4. If diff > D, add diff to ans.
5. After the loop ends, output ans.

Complexity

• Time Complexity: \(O(N \log N)\)
  • Sorting \(N\) elements takes \(O(N \log N)\) time. The subsequent loop runs in \(O(N)\) time, making the sorting step the bottleneck. Since \(N \leq 10^6\), this easily runs within the time limit.
• Space Complexity: \(O(N)\)
  • It uses \(O(N)\) memory to store the array \(A\) of input tempo values.

Implementation Points

• Preventing Overflow: The tempo values \(A_i\) can be up to \(10^9\), and the total discomfort (the answer) can exceed the maximum limit of a 32-bit signed integer (int type, which is about \(2 \times 10^9\)). Therefore, you should use a 64-bit integer type (such as long long in C++) for the variable storing the answer and the array storing the tempo values.

• Fast I/O: Since \(N\) can be as large as \(10^6\), in C++, you can significantly reduce the execution time by optimizing std::cin and std::cout (using ios_base::sync_with_stdio(false); cin.tie(NULL);).

  Source Code

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    // 高速入出力
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    long long D;
    if (!(cin >> N >> D)) return 0;

    vector<long long> A(N);
    for (int i = 0; i < N; ++i) {
        cin >> A[i];
    }

    // テンポ値を昇順にソート
    sort(A.begin(), A.end());

    long long ans = 0;
    // 隣り合うテンポ値の差が D より大きい場合、その差を違和感スコアとして加算する
    for (int i = 0; i < N - 1; ++i) {
        long long diff = A[i+1] - A[i];
        if (diff > D) {
            ans += diff;
        }
    }

    cout << ans << "\n";

    return 0;
}

---

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