【题解】摆渡车
题目链接
解题思路
正解是斜率优化,但是我不会
很容易想到是以时间作为下标dp的。但是由于时间复杂度会超,我们发现有用时间只有nm。所以对于其他的t-nm的时间可以用O(1)直接求出。为了快速求出i-j区间内的等候时间,可以记录人数的前缀和和到达时间的前缀和。等候时间计算公式就是 $i*(cnt_i-cnt_{i-m})-sum_i+sum_{i-m}$
代码
#include<bits/stdc++.h>
using namespace std;
const int MAXN=4e6+5000;
int n,m;
int temp[505];
int t[505];
int tot=0;
int dp[MAXN];
int sum[MAXN];//到达时间和
int cnt[MAXN];//总人数
const int inf=1e9+7;
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d",&temp[i]);
tot=max(tot,temp[i]);
cnt[temp[i]]++;
sum[temp[i]]+=temp[i];
}
for(int i=1;i<=tot+m;i++){
cnt[i]+=cnt[i-1];
sum[i]+=sum[i-1];
}
for(int i=1;i<=tot+m;i++){
if(i>=m&&cnt[i]==cnt[i-m]){
dp[i]=dp[i-m]+i*(cnt[i]-cnt[i-m])-sum[i]+sum[i-m];
continue;
}
dp[i]=cnt[i]*i-sum[i];
for(int j=max(0,i-m-m+1);j<=i-m;j++){
dp[i]=min(dp[i],dp[j]+i*(cnt[i]-cnt[j])-sum[i]+sum[j]);//j到i来的人等待的时间
}
}
int ans=inf;
for(int i=tot;i<=tot+m;i++){
ans=min(ans,dp[i]);
}
printf("%d",ans);
return 0;
}
本文链接:http://kaispace.com.cn/index.php/archives/722/
如果未注明出处,复制公开后需将注明本博客链接。打赏作者