本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-02-08 19:26:30

题传

思路

首先，朴素的 dp 转移时容易的。 设 $f_i$ 表示到时刻 $i$，且 $i$ 作为最后一次发车时间的总共的最小代价，然后用前缀和优化一下，令 $cnt_i$ 表示 $i$ 时刻之前的人的数量，$sum_i$ 表示 $i$ 时刻之前所有人的时间之和。

显然有：

$$f_i=\min_{0\le j \le i-m} f_j+i \times (cnt_i-cnt_j) -(sum_i-sum_j)$$

朴素优化

首先，考虑一定不会有一个长于 $m$ 的时间段使得没有任何一班车，因此我们可以将转移的下界设为 $i-2m$，时间复杂度 $O(tm)$。

其次，我们考虑，$t$ 很大，但 $m$ 很小，说明一定存在一些长为 $m$ 的区间一个人都没有，所以对于这样的区间，我们可以直接令 $f_i=f_{i-m}$。

至此，复杂度优化到了 $O(nm^2+t)$，可以通过。

斜率优化

将 dp 转移的式子进行拆分、移项，可得到以下的式子：

$$f_j+sum_j=i\times cnt_j+(f_i-cnt_i\times i+sum_i)$$

与一次函数的解析式 $y=kx+b$ 进行对比，可以发现：

$ y\to f_j+sum_j$

$k\to i$

$x\to cnt_j$

$b\to f_i-cnt_i\times i+sum_i$

也就是说，dp 转移方程是一个一次函数。

可以将前面的每一个状态看作是一个坐标为 $(cnt_j,f_j+sum_j)$ 的点，那么，在每次转移的过程中，我们就是要找到一个点，使得经过这个点的、斜率为 $i$ 的直线与 $y$ 轴的交点的纵坐标最小。

那么，其实就是求与前面所有的状态表示的点组成的凸包相切的直线。

由于求的是最小值，于是只维护下凸包即可。

可以用单调栈维护凸包。

由于斜率单调递增，于是可以使用单调队列，每次把不符合要求的点直接剔除。

时间复杂度 $O(t)$。

Code

#include <bits\/stdc++.h>
#define endl '\n'
#define int long long
#define fi first
#define se second
using namespace std;
const int N=4e6+100+10;
const int inf=0x3f3f3f3f3f3f3f3f;
pair<int,int> q[N];
int n,m;
int t;
int cnt[N];
int sum[N];
int f[N];
int l,r;
double slope(pair<int,int> x,pair<int,int> y)
{
    if(x.fi==y.fi) return (x.se>y.se?-inf:inf);
    return (double)(y.se-x.se)\/(double)(y.fi-x.fi);
}
int ans=inf;
signed main()
{
	\/\/freopen(".in","r",stdin);
    \/\/freopen(".out","w",stdout);
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(false);
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
	    int x;
	    cin>>x;
	    cnt[x]++;
	    sum[x]+=x;
	    t=max(t,x);
    }
    for(int i=1;i<=t+m;i++) sum[i]+=sum[i-1],cnt[i]+=cnt[i-1];
    l=1;
    for(int i=0;i<=m-1;i++) f[i]=i*cnt[i]-sum[i];
    for(int i=m;i<t+m;i++)
    {
        while(l<r&&slope(q[r-1],q[r])>slope(q[r],{cnt[i-m],f[i-m]+sum[i-m]})) r--;
        q[++r]={cnt[i-m],f[i-m]+sum[i-m]};
        while(l<r&&slope(q[l],q[l+1])<i) l++;
        f[i]=q[l].se-i*q[l].fi+i*cnt[i]-sum[i];
    }
    for(int i=t;i<t+m;i++) ans=min(ans,f[i]);
    cout<<ans;
    return 0;
}