题解：B4281 [蓝桥杯青少年组国赛 2023] 月球疏散行动

YZren · 2025-04-25 18:09:05 · 题解

题目传送门

思路

• 此题与摆渡车一模一样，很容易想到一个 DP 方程 dp_i=\min\limits_{j=1}^{i-m} (dp_j+sum_i-sum_j) 其中 dp_i 表示前 i 时刻到达的所有学生等待的最小时间。

• 很明显直接做肯定超时，所以需要优化。

• 首先进行前缀和优化，由于 sum_i 不好直接处理，所以分为 tim_i 表示前 i 时刻到达的总人数和 s_i 表示前 i 时刻所有学生到达的总时间，那么 sum_i-sum_j=(tim_i-tim_j)\times i-s_i+s_j 这就可以优化 DP 方程。

• 这样还是会超时，注意到 DP 方程为 dp_i=\min\limits_{j=1}^{i-m}(-tim_j\times i+s_j+dp_j)+tim_i\times i-s_i 很明显可以使用斜率优化，维护下凸壳即可。

• 推一下斜率方程，先令 k<j<i-m+1 并且从 j 转移更优，则 -tim_j\times i+s_j-dp_j<-tim_k\times i+s_k+dp_k 化简可得，先令 G_i=s_i+dp_i 那么 i>\frac{G_j-G_k}{tim_j-tim_k} 就是斜率方程了。

• 有了斜率方程，我们就可以用单调队列优化了，不会的可以先学一下斜率优化。

Code

#include<bits/stdc++.h>
#define endl "\n"
#define f(i,j,k) for(int i=j;i<=k;i++)
#define F(i,j,k) for(int i=j;i>=k;i--)
using namespace std;
const int maxn=4e6+10;
inline int read(){
    int x=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
    return x*f;
}
inline void write(int x){
    if(x<0) {x=~(x-1); putchar('-');}
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
int n=read(),m=read(),tim[maxn],dp[maxn],ans,s[maxn],que[maxn],L=1,R,u,maxx;
inline double slop(int k,int j){
    int up=dp[j]+s[j]-dp[k]-s[k];
    if(tim[j]==tim[k]) return (double)up/1e-9;
    else return (double)(up/(tim[j]-tim[k]));
}
inline void work(){ 
    f(i,1,n) u=read(),tim[u]++,s[u]+=u,maxx=max(maxx,u);
    maxx+=m-1; f(i,1,maxx) tim[i]+=tim[i-1],s[i]+=s[i-1];
    f(i,1,maxx){
        if(i>=m){
            while(L<R&&slop(que[R-1],que[R])>=slop(que[R],i-m)) R--;
            que[++R]=i-m;
        }
        while(L<R&&slop(que[L],que[L+1])<=i) L++;
        dp[i]=tim[i]*i-s[i];
        if(L<=R) dp[i]=min(dp[i],dp[que[L]]+(tim[i]-tim[que[L]])*i-s[i]+s[que[L]]);
    }
    ans=dp[maxx-m+1]; f(i,maxx-m+1,maxx) ans=min(ans,dp[i]);
    write(ans);
}
signed main(){work();return !!!!!("YZren");}