题目链接

解题思路

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

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

如果未注明出处，复制公开后需将注明本博客链接。
打赏作者