本文章由 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
*\/
鲁ICP备2025150228号