#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1020;
int dp[N][N][2];
int x[N];
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);
    int n,k;cin>>n>>k;
    for(int i=1;i<=n;i++)cin>>x[i];
    sort(x+1,x+1+n);
    int p=upper_bound(x+1,x+1+n,k)-x-1;
    memset(dp,0x3f,sizeof dp);
    if(p>0)dp[p][p][0]=dp[p][p][1]=(k-x[p])*n;
    if(p<n)dp[p+1][p+1][0]=dp[p+1][p+1][1]=(x[p+1]-k)*n;
    for(int l=2;l<=n;l++){
        for(int i=max(p-l+1,1ll);i<=min(p+1,n-l+1);i++){
            int j=i+l-1;
            dp[i][j][0]=min({dp[i][j][0],dp[i+1][j][0]+(n-l+1)*(x[i+1]-x[i]),dp[i+1][j][1]+(n-l+1)*(x[j]-x[i])});
            dp[i][j][1]=min({dp[i][j][1],dp[i][j-1][1]+(n-l+1)*(x[j]-x[j-1]),dp[i][j-1][0]+(n-l+1)*(x[j]-x[i])});
        }
    }
    cout<<min(dp[1][n][0],dp[1][n][1]);
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll lnf = 0x3f3f3f3f3f3f3f3f;
const int maxn = 1e3 + 20;
int n, k, s, x[maxn];
ll dp[2][maxn][2];
int main () {
    scanf ("%d%d", &n, &k);
    for (int i = 1; i <= n; ++i) {
        scanf ("%d", &x[i]);
    }
    x[++n] = k;
    sort (x + 1, x + n + 1);
    s = lower_bound (x + 1, x + n + 1, k) - x;
    int f = 0;
    memset (dp[f], 0x3f, sizeof (dp[f]));
    dp[f][s][0] = dp[f][s][1] = 0ll;
    for (int i = s; i; --i) {
        f ^= 1;
        if (i != s) {
            ll dis = x[s] - x[i], num = n - (s - i);
            dp[f][s][0] = min (
                dp[!f][s][0] + num * (x[i + 1] - x[i]),
                dp[!f][s][1] + num * dis
            );
            dp[f][s][1] = lnf;
        }
        for (int j = s + 1; j <= n; ++j) {
            ll dis = x[j] - x[i], num = n - (j - i);
            dp[f][j][0] = min (
                dp[!f][j][0] + num * (x[i + 1] - x[i]),
                dp[!f][j][1] + num * dis
            );
            dp[f][j][1] = min (
                dp[f][j - 1][0] + num * dis,
                dp[f][j - 1][1] + num * (x[j] - x[j - 1])
            );
        }
    }
    printf ("%lld\n", min (dp[f][n][0], dp[f][n][1]));
    return 0;
}

不知道谁的code放一下hansang写的太丑了不放：

#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <queue>
#include <iostream>
#include <set>
using namespace std;
#define N 1005
long long f[N][N],g[N][N];
int n,L,a[N];
int main()
{
    memset(f,0x3f,sizeof(f));memset(g,0x3f,sizeof(g));
    scanf("%d%d",&n,&L);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    sort(a+1,a+n+1);
    int p=lower_bound(a+1,a+n+1,L)-a;
    if(p!=1)f[p-1][1]=g[p-1][1]=1ll*n*(L-a[p-1]);
    if(a[p]>=L)f[p][1]=g[p][1]=1ll*n*(a[p]-L);
    for(int i=2;i<=n;i++)
    {
        for(int j=1;j<=n-i+1;j++)
        {
            int k=i+j-1;
            f[j][i]=min(f[j+1][i-1]+(n-i+1)*(a[j+1]-a[j]),g[j+1][i-1]+(n-i+1)*(a[k]-a[j]));
            g[j][i]=min(f[j][i-1]+(a[k]-a[j])*(n-i+1),g[j][i-1]+(a[k]-a[k-1])*(n-i+1));
        }
    }
    printf("%lld\n",min(f[1][n],g[1][n]));
    return 0;
}

那就再来放一下 cff 写的 code：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1020;
int dp[N][N][2];
int x[N];
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);
    int n,k;cin>>n>>k;
    for(int i=1;i<=n;i++)cin>>x[i];
    sort(x+1,x+1+n);
    int p=upper_bound(x+1,x+1+n,k)-x-1;
    memset(dp,0x3f,sizeof dp);
    if(p>0)dp[p][p][0]=dp[p][p][1]=(k-x[p])*n;
    if(p<n)dp[p+1][p+1][0]=dp[p+1][p+1][1]=(x[p+1]-k)*n;
    for(int l=2;l<=n;l++){
        for(int i=max(p-l+1,1ll);i<=min(p+1,n-l+1);i++){
            int j=i+l-1;
            dp[i][j][0]=min({dp[i][j][0],dp[i+1][j][0]+(n-l+1)*(x[i+1]-x[i]),dp[i+1][j][1]+(n-l+1)*(x[j]-x[i])});
            dp[i][j][1]=min({dp[i][j][1],dp[i][j-1][1]+(n-l+1)*(x[j]-x[j-1]),dp[i][j-1][0]+(n-l+1)*(x[j]-x[i])});
        }
    }
    cout<<min(dp[1][n][0],dp[1][n][1]);
    return 0;
}

EasonLiang 码风优良常数小，所以再放一下他的 code:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll lnf = 0x3f3f3f3f3f3f3f3f;
const int maxn = 1e3 + 20;
int n, k, s, x[maxn];
ll dp[2][maxn][2];
int main () {
    scanf ("%d%d", &n, &k);
    for (int i = 1; i <= n; ++i) {
        scanf ("%d", &x[i]);
    }
    x[++n] = k;
    sort (x + 1, x + n + 1);
    s = lower_bound (x + 1, x + n + 1, k) - x;
    int f = 0;
    memset (dp[f], 0x3f, sizeof (dp[f]));
    dp[f][s][0] = dp[f][s][1] = 0ll;
    for (int i = s; i; --i) {
        f ^= 1;
        if (i != s) {
            ll dis = x[s] - x[i], num = n - (s - i);
            dp[f][s][0] = min (
                dp[!f][s][0] + num * (x[i + 1] - x[i]),
                dp[!f][s][1] + num * dis
            );
            dp[f][s][1] = lnf;
        }
        for (int j = s + 1; j <= n; ++j) {
            ll dis = x[j] - x[i], num = n - (j - i);
            dp[f][j][0] = min (
                dp[!f][j][0] + num * (x[i + 1] - x[i]),
                dp[!f][j][1] + num * dis
            );
            dp[f][j][1] = min (
                dp[f][j - 1][0] + num * dis,
                dp[f][j - 1][1] + num * (x[j] - x[j - 1])
            );
        }
    }
    printf ("%lld\n", min (dp[f][n][0], dp[f][n][1]));
    return 0;
}