动态规划($O(mt)$100pts)

• 状态表示$f[i]$表示时刻$i$发车的所有人的最少等待时间
• 状态计算:枚举上一辆发车的时刻

#include<bits/stdc++.h>
using namespace std;
const int N=4e6+10;
int ans=1e9;
int cnt[N],sum[N],f[N];
//cnt[t]表示在前t个时刻一共出现的人数
//sum[t]表示在前t个时间，所有人的等待时间 
//f[i]表示从时刻i开始走的所有学生的等待时间 
int main()
{
	
	int n,m,t,T=0;
	//T表示最后一个到的人的时间点
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>t;
		t++;
		T=max(T,t);
		cnt[t]++,sum[t]+=t;	
	} 
	for(int i=1;i<T+m;i++)
	{
		cnt[i]+=cnt[i-1];//人数前缀和 
		sum[i]+=sum[i-1]; //所有i时刻的时间前缀和 
	}
	for(int i=1;i<T+m;i++)
	{
		f[i]=i*cnt[i]-sum[i];//只有一辆车
		for(int j=max(0,i-2*m);j<=i-m;j++) //枚举上个摆渡车时刻
		{
			f[i]=min(f[i],f[j]+(cnt[i]-cnt[j])*i-(sum[i]-sum[j]));
		} 
	}
	for(int i=T;i<T+m;i++) //枚举T开始的区间为m长度 
	{
		ans=min(ans,f[i]);
	}
	cout<<ans;
	return 0;
}

动态规划($nm^2$ 100pts)

• 可以将区间长度为$m$且没有人的区间跳过

#include<bits/stdc++.h>
using namespace std;
const int N=4e6+10;
int ans=1e9;
int cnt[N],sum[N],f[N];
//cnt[t]表示在前t个时刻一共出现的人数
//sum[t]表示在前t个时间，所有人的等待时间 
//f[i]表示从时刻i开始走的所有学生的等待时间 
int main()
{
	
	int n,m,t,T=0;
	//T表示最后一个到的人的时间点
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>t;
		t++;
		T=max(T,t);
		cnt[t]++,sum[t]+=t;	
	} 
	for(int i=1;i<T+m;i++)
	{
		cnt[i]+=cnt[i-1];//人数前缀和 
		sum[i]+=sum[i-1]; //时间前缀和 
	}
	for(int i=1;i<T+m;i++)
	{
		if(i>=m&&cnt[i]==cnt[i-m]) //长度为m这段没有人 
		{
			f[i]=f[i-m];
			continue;
		}
		f[i]=i*cnt[i]-sum[i];//初始化 
		for(int j=max(0,i-2*m);j<=i-m;j++) //枚举上个摆渡车时刻
		{
			f[i]=min(f[i],(cnt[i]-cnt[j])*i-(sum[i]-sum[j])+f[j]);
		} 
	}
	for(int i=T;i<T+m;i++) //枚举T开始的区间为m长度 
	{
		ans=min(ans,f[i]);
	}
	cout<<ans;
	return 0;
}