DP
很明显能想到 DP。
状态设计
不妨令 $t$ 从小到大有序，设 $dp_{i,j}$ 表示前 $i$ 个人在第 $i$ 个人等待了 $j$ 时刻时全部上车的最短时间。
状态转移
从其他状态转移到 $dp_{i,j}$ 不是很好做，因此可以从 $dp_{i,j}$ 转移到其他状态。
枚举一个 $k$，表示前 $i+k$ 个人都上车，且第 $i+1\sim i+k$ 个人一起上车。
则可以计算得出第 $i+k$ 个人的等待时间：
\[pl=\max((t_i+j)+m-t_{i+k},0)\]和 $0$ 取 $\max$ 是因为有可能车已经到了，但是第 $i+k$ 个人还没有开始等待。
则有：
\[dp_{i+k,pl}\leftarrow\min\left(dp_{i+k,pl},dp_{i,j}+\sum_{l=i+1}^{i+k}(t_{i+k}+pl-t_i)\right)\]其中，$\sum\limits_{l=i+1}^{i+k}(t_{i+k}+pl-t_i)$ 表示第 $i+1\sim i+k$ 个人的总等车时间。
化简，可以得到：
\[dp_{i+k,pl}\leftarrow\min\left(dp_{i+k,pl},dp_{i,j}+k(t_{i+k}+pl)-\sum_{l=i+1}^{i+k}t_i\right)\]很明显，做一个 $t$ 的前缀和即可单次实现 $\mathcal O(1)$ 转移，总转移复杂度 $\mathcal O(n)$。
AC 代码
时间复杂度：$\mathcal O\left(n^2m\right)$，状态量 $\mathcal O(nm)$，转移 $\mathcal O(n)$。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
//#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<ctime>
#include<deque>
#include<queue>
#include<stack>
#include<list>
using namespace std;
constexpr const int N=500,M=100,T=4e6;
int n,m,t[N+1],sum[N+1],dp[N+1][M+1];
int main(){
/*freopen("test.in","r",stdin);
freopen("test.out","w",stdout);*/
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>t[i];
}
sort(t+1,t+n+1);
for(int i=1;i<=n;i++){
sum[i]=sum[i-1]+t[i];
}
memset(dp,0x3f,sizeof(dp));
t[0]=-(1<<30);
dp[0][0]=0;
for(int i=0;i<=n;i++){
for(int j=0;j<=min(m-1,t[i+1]-t[i]);j++){
for(int k=1;i+k<=n;k++){
int pl=max(t[i]+j+m-t[i+k],0);
dp[i+k][pl]=min(dp[i+k][pl],dp[i][j]+k*(pl+t[i+k])-(sum[i+k]-sum[i]));
}
}
}
int ans=dp[n][0];
for(int i=1;i<m;i++){
ans=min(ans,dp[n][i]);
}
cout<<ans<<'\n';
cout.flush();
/*fclose(stdin);
fclose(stdout);*/
return 0;
}
