摆渡车(常规+斜率优化）

__S08577__ · 2025-02-08 17:16:22 · 题解

题意

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

思路

该题显然用动态规划。

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

不难发现：

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

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

不难发现：

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

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

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

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

可将式子优化为：

可是，复杂度仍然爆炸，只能去的 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

 */