P5017 [NOIP 2018 普及组] 摆渡车 题解

· · 题解

题传

思路

首先，朴素的 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;
}