Overview

This problem asks us to find the minimum possible sum of discomfort scores when we arrange the tempo values in any order, where discomfort occurs if there is no similar song played in the past.

In conclusion, the answer can be found by sorting the tempo values in ascending order and summing up only the differences between adjacent values that are strictly greater than \(D\).

Analysis

First, let the tempo values sorted in ascending order be:

\(A_1 \leq A_2 \leq \cdots \leq A_N\)

Let’s focus on the difference between adjacent tempo values, \(A_i - A_{i-1}\).

Case where the difference is \(D\) or less

If \(A_i - A_{i-1} \leq D\), then \(A_i\) is “similar” to the immediately preceding song \(A_{i-1}\).

Therefore, if we play them in ascending order, the discomfort score for this song can be \(0\).

Case where the difference is greater than \(D\)

Consider the case where \(A_i - A_{i-1} > D\).

In this case, there is always a difference greater than \(D\) between any song with a tempo of \(A_{i-1}\) or less and any song with a tempo of \(A_i\) or more.

In other words, when crossing this boundary, at the moment we play a song from the other group for the first time, there is no similar song played in the past.

Therefore, no matter what order we choose, crossing this boundary will require a discomfort cost of at least \(A_i - A_{i-1}\).

Ascending order is optimal

If we play the songs in ascending order:

• If the difference with the adjacent song is \(D\) or less, the discomfort score is \(0\).
• If the difference with the adjacent song is greater than \(D\), the discomfort score is that difference.

Therefore, we only need to sum up the differences that satisfy:

\(A_i - A_{i-1} > D\)

when sorted in ascending order.

For example, if:

\(A = [1, 3, 10, 12, 20]\), \(D = 2\)

Considering them in ascending order:

• Since \(3 - 1 = 2 \leq D\), the cost is \(0\).
• Since \(10 - 3 = 7 > D\), the cost is \(7\).
• Since \(12 - 10 = 2 \leq D\), the cost is \(0\).
• Since \(20 - 12 = 8 > D\), the cost is \(8\).

Therefore, the answer is:

\(7 + 8 = 15\)

A naive approach of trying all permutations would take \(N!\) ways, which is far too slow for \(N \leq 10^6\). Thus, we solve it efficiently by sorting and looking only at the differences between adjacent elements.

Algorithm

1. Sort the array \(A\) in ascending order.
2. Initialize the answer as \(ans = 0\).
3. For each \(i\) from \(1\) to \(N-1\):
   • If \(A_i - A_{i-1} > D\), add the difference to \(ans\).
4. Output \(ans\).

Complexity

• Time Complexity: \(O(N \log N)\)
• Space Complexity: \(O(N)\)

The sorting step is dominant.

Implementation Points

Since \(A_i\) and \(D\) can be up to \(10^9\), it is safe to handle the differences and the final answer using a 64-bit integer type (such as long long in C++).

Also, when \(N = 1\), there is only one song to play, so the total discomfort is \(0\). The loop will naturally not execute, and \(0\) will be output correctly.

Source Code

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    long long D;
    cin >> N >> D;

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

    sort(A.begin(), A.end());

    long long ans = 0;
    for (int i = 1; i < N; i++) {
        long long diff = A[i] - A[i - 1];
        if (diff > D) ans += diff;
    }

    cout << ans << '\n';
    return 0;
}

---

This editorial was generated by gpt-5.5-high.