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

题意

有 $n$ 个人在等车，第 $i$ 个人从 $t_i$ 时刻开始等车。摆渡车来回一趟需要 $m$ 分钟。求所有人最小等车时间。

思路

该题显然用动态规划。

不妨设 $f_i$ 为从开始到第 $i$ 时刻每个人最小等车时间。

不难发现：

$$f_i=\min_{j \le i-m}(f_j+\sum_{j < t_k \le i} i-t_k)$$

但是，这个方程中的 $\sum_{j < t_k \le i} i-t_k$ 很难处理。我们不妨将其拆开：

$$\sum_{j < t_k \le i} i-t_k \\ =\sum_{j < t_k \le i} i -\sum_{j < t_k \le i} t_k$$

看见求和，我们不难想到使用前缀和。不妨设 $cnt_i$ 为从开始到 $i$ 时刻有多少人等车，$sum_i$ 为从开始到 $i$ 时刻的位置之和。

不难发现：

$$\sum_{j < t_k \le i} i-t_k \\ =\sum_{j < t_k \le i} i -\sum_{j < t_k \le i} t_k \\ = i \times (cnt_i-cnt_j)-(sum_i-sum_j)$$

所以，状态转移方程即为：

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

最后，由于最后一个人的到达时间为 $t$，我们只需要查询 $\min_{1 \le i \le t+k} f_i$

但是，时间复杂度为 $O(t^2)$ 只能拿到$50$ $pts$。

不妨进行优化，不难发现，当时间小于 $i-2m$ 时，乘客肯定已经坐上车了，所以无需考虑 $i-2m$ 之前的情况。

可将式子优化为：

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

可是，复杂度仍然爆炸，只能去的 $75$ $pts$。

我们不难发现，摆渡车以 $m$ 为一个周期。如果从 $i-m$ 到 $i$ 没有人上车，则这段区间为无用区间，令 $f_i=f_{i-m}$。

这样，我们就可以AC了。

代码

#include<iostream>
#include<cstdio>
#include<cmath>
#include<string>
#include<cstring>
#include<iomanip>
#include<algorithm>
#include<vector>
#include<stack>
#include<map>
#include<queue>
#include<set>


using namespace std;

#define int long long
#define ll long long
#define Endl cout<<endl;
#define ENdl Endl
#define xy cout<<"xy";
#define yx cout<<"yx";
#define pii pair<int,int>
#define lowbit(x) x&(-x)
#define fi first
#define se second
#define fst ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

const int N=4e6+10;\/\/注意修改
const int mod=1e9+7;
const int Max=0x3f3f3f3f3f;

int n,m;
int a[N];
int f[N],cnt[N],sum[N];


\/*
f_i=min j<=i-m(f_j+sigma i-t_k)
 *\/
signed main(){
    
\/\/   freopen("a.in","r",stdin);
\/\/   freopen("a.out","w",stdout);
    cin>>n>>m;
    int t=0;
    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++){
        cnt[i]+=cnt[i-1];
        sum[i]+=sum[i-1];
    }
    for(int i=0;i<t+m;i++){
        if(i>=m&&cnt[i]==cnt[i-m]){
            f[i]=f[i-m];
            continue;
        }
        f[i]=cnt[i]*i-sum[i];
        for(int j=max(i-m-m+1,0ll);j<=i-m;j++){
            f[i]=min(f[i],f[j]+i*(cnt[i]-cnt[j])-(sum[i]-sum[j]));
        }
        
    }
    int res=Max;
    for(int i=t;i<t+m;i++){
        res=min(res,f[i]);
    }
    cout<<res;

    return 0;
}



\/*
 1
 5 3
 2 4 5

 *\/

斜率优化版

#include<iostream>
#include<cstdio>
#include<cmath>
#include<string>
#include<cstring>
#include<iomanip>
#include<algorithm>
#include<vector>
#include<stack>
#include<map>
#include<queue>
#include<set>


using namespace std;

#define int long long
#define ll long long
#define Endl cout<<endl;
#define ENdl Endl
#define xy cout<<"xy";
#define yx cout<<"yx";
#define pii pair<int,int>
#define lowbit(x) x&(-x)
#define fi first
#define se second
#define fst ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

const int N=4e6+10;\/\/注意修改
const int mod=1e9+7;
const int Max=0x3f3f3f3f3f;

int n,m;
int a[N];
int f[N],cnt[N],sum[N],q[N];

double get_k(int x,int y){
    return double(f[y]+sum[y]-f[x]-sum[x])\/(cnt[x]==cnt[y]?1e-9:  cnt[y]-cnt[x]);
}
\/*
f_i=min j<=i-m(f_j+sigma i-t_k)
 *\/
signed main(){
    
\/\/   freopen("a.in","r",stdin);
\/\/   freopen("a.out","w",stdout);
    cin>>n>>m;
    int t=0;
    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++){
        cnt[i]+=cnt[i-1];
        sum[i]+=sum[i-1];
    }
    int l=1,r=0;
    for(int i=0;i<t+m;i++){
        if(i-m>=0){
            while(l<r&&get_k(q[r-1],q[r])>=get_k(q[r],i-m)){
                r--;
            }
            q[++r]=i-m;
        }
        while(l<r&&get_k(q[l],q[l+1])<=i) l++;
        f[i]=i*cnt[i]-sum[i];
        if(l<=r){
            f[i]=min(f[i],f[q[l]]+i*(cnt[i]-cnt[q[l]])-(sum[i]-sum[q[l]]));
        }
    }
    int res=Max;
    for(int i=t;i<t+m;i++){
        res=min(res,f[i]);
    }
    cout<<res;

    return 0;
}



\/*
 1
 5 3
 2 4 5

 *\/