题目链接

解题思路

正解是斜率优化，但是我不会

很容易想到是以时间作为下标 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;
}