题解：P7214 [JOISC 2020] 治療計画

· · 题解

信竞生涯第一道黑题。

题意

JOI 村庄爆发了疫情，你作为总理需要选择方案治愈大家！给定一个长度为 n 的区域和 m 个治疗计划，每个计划有执行时间 t，治疗区间 [l,r] 和成本 c。要求选择一系列计划，使得它们能够从区域最左端 l=1 连续覆盖到最右端 r=n，且任意两个衔接的计划 i 和 j 必须满足 r[i]-l[j]\ge|t[i]-t[j]|（确保治疗覆盖的连续性）。目标是在所有满足条件的计划组合中找出总成本最小的方案，若不存在可行解则输出 -1。

思路

问题转化

如果两个计划 i 和 j 满足 r[i]-l[j]\ge|t[i]-t[j]|，则它们可以衔接（即 i 可以接在 j 后面），那就可以将这个问题转化为最短路问题：

结点：每个计划 i。

边：如果 i 和 j 可以衔接，则让 i 连向 j，边权为 c[j]。

初始点：所有 l[i]=1 的计划（起点）。

目标点：所有 r[i]=m 的计划（终点）。

但是直接建图时间复杂度会来到 O(n^2)，这在 n=10^5 时是不可行的。

考虑优化

使用 Dijkstra 配合线段树优化松弛过程：

  1. 想要两个计划 i 和 j 可以衔接，那么就必须满足 r[i]-l[j]\ge|t[i]-t[j]|，考虑拆解这个不等式：

    • 如果 t[i]\ge t[j]（i 比 j 晚执行），则条件变为 r[i]-t[i]\ge l[j]-t[j]。

    • 如果 t[i]<t[j]（j 比 i 晚执行），则条件变为 r[i]+t[i]\ge l[j]+t[j]。

  2. 由上，容易想到使用线段树维护，快速查询满足 l[j]-t[j]\leq r[i]-t[i] 或 l[j]+t[j]\leq r[i]+t[i] 的计划 j。

我们维护两棵线段树，分别存储：

  1. Dijkstra

    • 初始化：创建 dist 数组统计距离，让所有 l[i]=1 的计划 i 作为起点，dist[i]=c[i]，并加入优先队列。其余计划的 dist[i] 赋为极大值，并插入线段树。

    • 核心部分（主循环）：取出当前 dist 数组中最小的计划 i，查询可以衔接的计划 j。

情况 1（t[i]\ge t[j]）：则在 LeftTree 中查询 l[j]-t[j]\leq r[i]-t[i] 的计划 j。

情况 2（t[i]<t[j]）：则在 RightTree 中查询 l[j]+t[j]\le r[i]+t[i] 的计划 j。

对于所有查询到的 j，检查 dist[j]>dist[i]+c[j]，如果是，则更新 dist[j] 并加入优先队列，后从线段树中移除 j（避免重复松弛）。

最终答案

在完成 Dijkstra 与线段树优化后，我们需要从所有能覆盖最右端（r[i]=n）的计划中找出最小的 dist[i]，打擂后输出即可。如果没有找到可行解，输出 -1。

AC Code

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
const long long INF=1e18;

int n,m; 
long long f[N];//f[i] 表示从某个起点到 i 的最小成本。
struct Plan{
    int t,l,r,c;
    bool operator<(const Plan& o)const{return t<o.t;}
}p[N]; 

vector<int>adj;
priority_queue<pair<long long,int>>q;
//线段树。
struct SegTree{
    int l,r,mid;
    long long minL,minR;//维护 l-t 和 l+t 的最小值。
    SegTree *ls,*rs;
    SegTree(int l,int r):l(l),r(r),minL(INF),minR(INF){
        if(r-l>1){
            mid=(l+r)>>1;
            ls=new SegTree(l,mid);
            rs=new SegTree(mid,r);
        }
    }
    //更新 pos 位置的值。
    void update(int pos,long long vl,long long vr){
        if(r-l==1){
            minL=vl;
            minR=vr;
            return;
        }
        pos<mid?ls->update(pos,vl,vr):rs->update(pos,vl,vr);
        minL=min(ls->minL,rs->minL);
        minR=min(ls->minR,rs->minR);
    }
    //查询可松弛的 j。
    void query(int ql,int qr,long long bound,bool type){
        if((type?minL:minR)>bound) return;
        if(r-l==1){
            adj.push_back(l);
            minL=minR=INF;
            return;
        }
        if(ql<mid) ls->query(ql,qr,bound,type);
        if(qr>mid) rs->query(ql,qr,bound,type);
        minL=min(ls->minL,rs->minL);
        minR=min(ls->minR,rs->minR);
    }
};

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>m; //n 是区域长度，m 是计划数量。

    for(int i=0;i<m;i++){ 
        cin>>p[i].t>>p[i].l>>p[i].r>>p[i].c;
        p[i].l--; //转换为 0-based。
    }
    sort(p,p+m);//时间排序。
    //Dijkstra 初始化。
    SegTree* rt=new SegTree(0,m);//线段树，管理 m 个计划。
    for(int i=0;i<m;i++){ 
        if(p[i].l==0){//可以覆盖左边界（起点）。
            f[i]=p[i].c;
            q.push({-f[i],i});//优先队列（最小堆）。
            rt->update(i,INF,INF);//已访问，不再处理。
        }else{
            rt->update(i,p[i].l-p[i].t,p[i].l+p[i].t);//未访问，存储可衔接条件。
            f[i]=INF;//初始距离无穷大。
        }
    }
    //Dijkstra。
    while(!q.empty()){
        int u=q.top().second; q.pop();
        adj.clear();
        //查询能衔接的左侧计划。
        rt->query(0,u,p[u].r-p[u].t,1);
        //查询能衔接的右侧计划。
        rt->query(u+1,m,p[u].r+p[u].t,0);
        for(int v:adj){//遍历所有可松弛的 v。
            if(f[v]>f[u]+p[v].c){
                f[v]=f[u]+p[v].c;
                q.push({-f[v],v});//更新距离。
            }
        }
    }

    long long ans=INF;
    for(int i=0;i<m;i++)
        if(p[i].r==n)ans=min(ans,f[i]);//检查是否能覆盖到最右端。
    if(ans==INF)cout<<-1;
    else cout<<ans;
    return 0;
}

特别鸣谢：