Summary

This problem asks us to find a playback order of \(N\) songs that minimizes the sum of penalties. A penalty is added only for songs that do not satisfy the condition: “the difference in tempo from some previously played song is at most \(D\)”.

Analysis

First, we sort the tempo values and group songs whose difference is at most \(D\) into connected components (groups). By playing songs within the same group in ascending (or descending) order, the difference between any song (from the second one onwards) and the immediately preceding song is guaranteed to be at most \(D\). Therefore, if we play songs within the same group consecutively, the discomfort score generated within the group will be \(0\).

Regarding transitions between groups, a discomfort score is always incurred when moving from a song in one group to a song in another group. To minimize the score, we need to minimize the transitions between groups, so it is optimal to play each group consecutively as a single block.

Here, each group has a “minimum value \(L\)” and a “maximum value \(R\)”. If we play a group in ascending order, the first song is \(L\) and the last song is \(R\). If we play it in descending order, the first song is \(R\) and the last song is \(L\). In other words, the end of any group will be either \(L\) or \(R\). We use dynamic programming (DP) to minimize the transition cost from the end of the previous group to the start of the next group.

Algorithm

1. Sort the array \(A\) in ascending order.
2. Divide the songs into groups such that the difference between adjacent elements is at most \(D\). Store the minimum value of each group in array L and the maximum value in array R.
3. Define the DP table as follows:
   • dp0: The minimum discomfort score after playing up to the \(i\)-th group, where the last song is L[i].
   • dp1: The minimum discomfort score after playing up to the \(i\)-th group, where the last song is R[i].
4. In the initial state (the 0-th group), the discomfort is 0, so we set dp0 = 0 and dp1 = 0.
5. The transitions to the \(i\)-th group are as follows:
   • When playing the current group in ascending order to end with R[i], the starting song is L[i]. The transition cost differs depending on whether the end of the previous group was L[i-1] or R[i-1]. next_dp1 = min(dp0 + |L[i] - L[i-1]|, dp1 + |L[i] - R[i-1]|)
   • When playing the current group in descending order to end with L[i], the starting song is R[i]. We calculate similarly: next_dp0 = min(dp0 + |R[i] - L[i-1]|, dp1 + |R[i] - R[i-1]|)
6. Update the DP for all groups, and the final answer will be min(dp0, dp1).

Complexity

• Time Complexity: \(O(N \log N)\) (dominated by sorting)
• Space Complexity: \(O(N)\)

Implementation Points

• Since \(N\) is as large as \(10^6\), fast I/O is required (e.g., using ios_base::sync_with_stdio(false); cin.tie(NULL); in C++).

• In C++, if you rely on abs() without caution, it can cause unintended behavior or overflow for long long types. To avoid this, you can either flip the sign directly using conditional branches or use std::abs properly (the provided code uses if statements for sign flipping).

• If there is only one group, no transitions between groups occur, so the discomfort score will be 0.

  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;
    cin >> N >> D;
    vector<long long> A(N);
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }
    sort(A.begin(), A.end());
    
    vector<long long> L, R;
    for (int i = 0; i < N; ) {
        int j = i;
        while (j + 1 < N && A[j+1] - A[j] <= D) {
            j++;
        }
        L.push_back(A[i]);
        R.push_back(A[j]);
        i = j + 1;
    }
    
    int M = L.size();
    if (M == 1) {
        cout << 0 << endl;
        return 0;
    }
    
    long long dp0 = 0; // ends at L[i-1]
    long long dp1 = 0; // ends at R[i-1]
    
    for (int i = 1; i < M; i++) {
        long long r_minus_l_prev0 = R[i] - L[i-1]; if (r_minus_l_prev0 < 0) r_minus_l_prev0 = -r_minus_l_prev0;
        long long r_minus_r_prev1 = R[i] - R[i-1]; if (r_minus_r_prev1 < 0) r_minus_r_prev1 = -r_minus_r_prev1;
        long long l_minus_l_prev0 = L[i] - L[i-1]; if (l_minus_l_prev0 < 0) l_minus_l_prev0 = -l_minus_l_prev0;
        long long l_minus_r_prev1 = L[i] - R[i-1]; if (l_minus_r_prev1 < 0) l_minus_r_prev1 = -l_minus_r_prev1;
        
        long long next_dp0 = min(dp0 + r_minus_l_prev0, dp1 + r_minus_r_prev1);
        long long next_dp1 = min(dp0 + l_minus_l_prev0, dp1 + l_minus_r_prev1);
        dp0 = next_dp0;
        dp1 = next_dp1;
    }
    
    cout << min(dp0, dp1) << endl;
    
    return 0;
}

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