思路

先把每个学生等车的时间 $t[i]$ 抽象成数轴上的一个点。

按贪心思想，摆渡车要么在 $t[i]$ 发车（即刚好有学生等车），要么在 $t[i]+m$ 发车（即摆渡车刚好回到）。

那么先插入 $n$ 个时间点 $t[i]+m$ ,再将 $2n$ 个点排序。

设 $f[i]$ 为在第 $i$ 个时间点发车时前所有学生的等车时间之和最小值，$cnt[i]$ 为在第 $i$ 个时间点前等车的学生数，$sum[i]$为在第 $i$ 个时间点前等车的学生的到达时间和，$las[i]$ 为在 $t$ 数组中最后一个小于等于 $t[i]-m$ 的下标。

如果想要在第 $i$ 个时间点发车，那么上一趟车只能在 $t[i]-m$ （ $t[i]$ 为插入新点后排序的数组）或 $t[i]-m$ 前发车。记上一次发车的时间点编号为 $j$ ，那么在区间$[j+1,i]$ 中的学生只能在 $t[i]$ 时上车，这一部分的学生的等候时间为 $(cnt[i]-cnt[j])*t[i]-(sum[i]-sum[j])$

则

$f[i] = \min\limits_{0\le j\le las[j]}\{f[j]+(cnt[i]-cnt[j])*t[i]-(sum[i]-sum[j])\}$

$\rm CODE$

#include<bits/stdc++.h>
#include<bits/stdc++.h>
#define N 505
using namespace std;
int n,m,ans;
struct point{
    int t,v;
    bool operator < (const point& x) const{
        return t<x.t;
    }
}t[N<<1];
int q[N<<1],head=1,tail=1;
int sum[N<<1],las[N<<1],f[N<<1],cnt[N<<1];
void solve()
{
    memset(f,0x3f,sizeof(f));
    f[0]=0;
    sort(t+1,t+1+n+n);

    for(int i=1; i<=n<<1; i++)
    {
        cnt[i]=cnt[i-1]+(bool)t[i].v;
        sum[i]=sum[i-1]+t[i].v; 
        while(head<tail && t[q[head+1]].t+m<=t[i].t) head++;
        q[++tail]=i;
        las[i]=q[head];
    }
    for(int i=1; i<=n<<1; i++)
    {
        for(int j=0; j<=las[i]; j++)
            f[i]=min(f[i],f[j]+(cnt[i]-cnt[j])*t[i].t-(sum[i]-sum[j]));
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    int en=0;
    for(int i=1; i<=n; i++)
    {
        scanf("%d",&t[i].t);
        t[i].v=t[i].t;
        t[i+n].t=t[i].t+m;
        en=max(en,t[i].t);
    }
    solve();
    int now=1;
    while(t[now].t!=en) now++;
    ans=0x3f3f3f3f;
    for(int i=now; i<=n<<1; i++) ans=min(ans,f[i]);
    printf("%d",ans);
    return 0;
}