The problem can be found here

My Thought Process

First of all, we can see that the bound for $n$ is quite small. It’s possible to have $O(n^3)$ complexity since it will only be $8 * 10^6$ operations. This also seems like a good problem to do DP on because of small constraints.

Let’s first just sort the array in non-increasing order because the order of them doesn’t matter right now. A good way to think about it is actually to basically pick some $n$ times to pull out the dishes and then assign each dish to each time.

If we sort the times, then each dish will just pair up with the same index. So $t_1[i]$ pair up with $t_2[i]$ where $t_2$ is just some random times we pick. This is because the first dish in the order should be pulled out the earliest so it would be paired up with the earliest time we picked and so on.

This allows to use dp. Let $dp[i][j]$ be the minimum unpleasent value sum if we consider the first $i$ values and have took out $j$ dishes.

The implementation will make it a lot more clear.

Implementation

#include <bits/stdc++.h>

using ll = long long;
#define pb push_back

using namespace std;

const int MOD = 1e9+7;
const int MAXN = 2e6+1;
const int INF = 2e9;    
const long long IINF = 2e18;

void solve() { 
    int n;
    cin >> n;

    vector<int> v(n+1);
    for(int i = 1; i <= n; ++i){cin >> v[i];}

    vector<vector<int>> dp(2 * n + 1, vector<int>(n+1, 1e9));

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

    dp[0][0] = 0;

    for(int i = 1; i <= 2 * n; ++i){
        dp[i][1] = min(dp[i-1][1], abs(i - v[1]));
        for(int j = n; j >= 2; --j){
            dp[i][j] = min(dp[i-1][j], dp[i-1][j-1] + abs(v[j] - i));
        }
    }

    cout << dp[2*n][n] << endl;
}

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin >> t;
    while(t--){
        solve();
    }

    return 0;
}

See here for the solution and another implementation.