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

liyancen · 2026-03-08 21:13:01 · 题解

比较典的斜率优化问题。

我们先考虑暴力怎么转移。

很显然，设 dp_i 表示在 i 时刻所有已经到达的人的等待时间的最小值。根据题目定义，有：

不难发现这样其实是 \cal O(n^3) 的，我们考虑如何优化。

关键优化的地方就是后面的那个式子，考虑如何转化成 \cal O(1) 的方式来计算。

考虑到符合条件的 T_i 所对应的最终节点都是 i，考虑通过维护前缀和的方式可以计算得出。不难发现，设 pos_i 表示在 i 时刻，总共已经有多少人到达（包含已经走了的），sumT_i 表示在 i 时刻，已经到达的人（包含已经走了的）的到达时间之和，即 T_i 之和。

那么 sumT_i-sumT_j 得到的答案就是 (j,i] 这个区间中，到达的人的 T_i 之和，pos_i-pos_j 就是这个区间到达的人数。

那么就有：

这样就可以把时间复杂度降到 \cal O(n^2)。

但是很显然，还是过不了，我们还要继续考虑优化。观察现有的状态转移方程。

展开有：

不难发现，当 i 固定时，i\times pos_i 和 sumT_i 也是固定的，那么就可以考虑斜率优化。

显然可以式子化成：

其中 y=dp_j+sumT_j，k=i，x=pos_j，b=dp_i+sumT_i-i\times pos_i。然后就做完了。

只不过要注意一下 i\le M 时不可以直接转移，可以提前处理就行。

然后，我的代码是二分查找的，所以说对于点的加入可以考虑延迟添加。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int INF=4e6+1000;

int n,M,maxT;
ll pos[INF],sumT[INF],dp[INF],ans=INT_MAX;
struct Node{ll a,b;int t;}q[INF];
int head=1,tail;

namespace Slope{
    inline bool check(int x,int y,ll k){return (q[y].b-q[x].b)<=k*(q[y].a-q[x].a);}
    inline int get_best(ll k){
        if (head==tail)return head;
        int l=head+1,r=tail,res=head;
        while (l<=r){
            int mid=(l+r)>>1;
            if (check(mid-1,mid,k))res=mid,l=mid+1;
            else r=mid-1;
        }
        return res;
    }
    inline void update(Node c){
        while (tail>head){
            Node a=q[tail-1],b=q[tail];
            if ((c.b-b.b)*(b.a-a.a)<=(b.b-a.b)*(c.a-b.a))tail--;
            else break;
        }
        q[++tail]=c;
    }
}
namespace yixing{
    inline void Main(){
        cin>>n>>M;
        for (int i=1;i<=n;i++){
            int t;cin>>t;
            maxT=max(maxT,t);
            pos[t]+=1,sumT[t]+=t;
        }
        for (int i=1;i<=maxT+M;i++)pos[i]+=pos[i-1],sumT[i]+=sumT[i-1];
        q[++tail]={0,0};
        for (int i=1;i<=maxT+M;i++){
            if (i-M>=0){
                Node ne_pos={pos[i-M],dp[i-M]+sumT[i-M]};
                Slope::update(ne_pos);
            } 
            int j=Slope::get_best(i);
            int x=q[j].a,y=q[j].b;
            int b=y-i*x;
            dp[i]=min(b-sumT[i]+i*pos[i],i*pos[i]-sumT[i]);
            if (i>=maxT)ans=min(ans,dp[i]);
        }
        cout<<ans;
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    yixing::Main();
    return 0;
}