来自 这篇笔记 第2部分。

由于AcWing的LaTeX有点奇怪，所以文中所有应该用 {} 表示的minmax全部采用小括号

题目链接

题意

有 $n$ 名同学要乘坐摆渡车从 $A$ 到 $B$，第 $i$ 位同学在第 $t_i$ 分钟去等车。有一辆摆渡车，容量无限大，从 $A$ 出发、 把车上的同学送到 $B$、再回到 $A$（去接其他同学），往返一趟总共花费 $m$ 分钟（上下车时间忽略不计）。要将所有同学都送到 $B$.

已知你可以任意安排摆渡车出发的时间，求所有人等车时间之和的最小值。摆渡车回到 $A$ 后可以即刻出发。

$n\leq 500,m\leq 100,0\leq t\leq 4e6$

思路

设 $f_i$ 表示到了时间点 $i$，所有同学等待时间最小和。可以写出方程：
$$ f_i=min( f_j+\sum_{j<t_k<\leq i} (i-t_k) ),j\leq i-m $$
前缀优化。设 $cnt_i$ 为 $i$ 时刻到达车站的学生个数，$sum_i$ 表示已经到达车站的学生到达时间总和。有方程：
$$ f_i=min( f_j+(cnt_i-cnt_j)\times i-(sum_i-sum_j)),j\leq i-m $$
看到了 $i,j$ 乘积！好，上斜优。首先来整理一下式子：
$$ f_i=min( f_j+sum_j-cnt_j\times i )+cnt_i\times i-sum_i $$
把 $min$ 去掉，转化成 $kx+b=y$ 的形式：
$$ f_j+sum_j=cnt_j\times i+f_i-cnt_i\times i+sum_i $$
把 $i$ 作为 $k$ ，$cnt_j$ 作为 $x$，剩余为 $b$ ，得到了直线方程。决策单调性转移即可。

但是这题还有一些问题需要处理：

1. $j\leq i-m$ 。采用分层入队，每当完成了 $f_i$ 的转移，就把 $i-m+1$ 这个决策点入队即可。
2. 有重点。也就是横坐标相等纵坐标不等，那么按位置判断 $inf/-inf$ 即可。
3. $f[]$ 需要初始化。 是第一个问题的延伸，因为前面 $m$ 个点没有初始值。暴力更新即可。

代码

#include <bits/stdc++.h>
#define ll long long
#define lb long double
using namespace std;
const ll T=9e6+10,inf=1e18;
ll n,m,mxt,cnt[T],sum[T],f[T],q[T],h,t,ans=inf;

lb Y( int num ) { return f[num]+sum[num]; }
lb X( int num ) { return cnt[num]; }
lb slope( int x,int y )
{
        if ( X(x)==X(y) ) return Y(y)>Y(x) ? inf*1.0 : inf*-1.0;
        return ( Y(y)-Y(x)) / ( X(y)-X(x) );
}

int main()
{
        scanf( "%lld%lld",&n,&m );
        for ( ll i=1,ti; i<=n; i++ )
        {
                scanf( "%lld",&ti ),mxt=max( ti,mxt );
                sum[ti]+=ti; cnt[ti]++;
        }
        for ( ll i=1; i<=mxt+m; i++ )
                sum[i]+=sum[i-1],cnt[i]+=cnt[i-1];

        h=t=1; q[t]=0;
        for ( int i=1; i<m; i++ ) f[i]=cnt[i]*i-sum[i];
        for ( int i=m; i<=mxt+m; i++ )
        {
                while ( h<t && slope(q[h],q[h+1])<=1.0*i ) h++;
                f[i]=f[q[h]]+(cnt[i]-cnt[q[h]])*i-(sum[i]-sum[q[h]]);
                while ( h<t && slope(q[t-1],q[t])>=slope(q[t],i-m+1) ) t--;
                q[++t]=i-m+1;
                if ( i>=mxt ) ans=min( ans,f[i] ); 
        }

        printf( "%lld",ans );
}