专栏文章

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

ddengrunze2608
P7214题解参与者 2已保存评论 2

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
2 条
当前快照
1 份
快照标识符
@mioa7sge
此快照首次捕获于
2025/12/02 15:54
3 个月前
此快照最后确认于
2025/12/02 15:54
3 个月前
查看原文
信竞生涯第一道黑题。

题意

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

思路

问题转化

如果两个计划 ii 和 jj 满足 r[i]−l[j]≥∣t[i]−t[j]∣r[i]-l[j]\ge|t[i]-t[j]|，则它们可以衔接（即 ii 可以接在 jj 后面），那就可以将这个问题转化为最短路问题：
结点：每个计划 ii。
边：如果 ii 和 jj 可以衔接，则让 ii 连向 jj，边权为 c[j]c[j]。
初始点：所有 l[i]=1l[i]=1 的计划（起点）。
目标点：所有 r[i]=mr[i]=m 的计划（终点）。
但是直接建图时间复杂度会来到 O(n2)O(n^2)，这在 n=105n=10^5 时是不可行的。

考虑优化

使用 Dijkstra 配合线段树优化松弛过程：
  1. 想要两个计划 ii 和 jj 可以衔接，那么就必须满足 r[i]−l[j]≥∣t[i]−t[j]∣r[i]-l[j]\ge|t[i]-t[j]|，考虑拆解这个不等式：
  • 如果 t[i]≥t[j]t[i]\ge t[j]（ii 比 jj 晚执行），则条件变为 r[i]−t[i]≥l[j]−t[j]r[i]-t[i]\ge l[j]-t[j]。
  • 如果 t[i]<t[j]t[i]<t[j]（jj 比 ii 晚执行），则条件变为 r[i]+t[i]≥l[j]+t[j]r[i]+t[i]\ge l[j]+t[j]。
  1. 由上，容易想到使用线段树维护，快速查询满足 l[j]−t[j]≤r[i]−t[i]l[j]-t[j]\leq r[i]-t[i] 或 l[j]+t[j]≤r[i]+t[i]l[j]+t[j]\leq r[i]+t[i] 的计划 jj。
我们维护两棵线段树，分别存储：
  • LeftTree：维护 l[j]−t[j]l[j]-t[j] 的最小值，用于查询 t[i]≥t[j]t[i]\ge t[j] 的情况。
  • RightTree：维护 l[j]+t[j]l[j]+t[j] 的最小值，用于查询 t[i]<t[j]t[i]<t[j] 的情况。
  1. Dijkstra
  • 初始化：创建 distdist 数组统计距离，让所有 l[i]=1l[i]=1 的计划 ii 作为起点，dist[i]=c[i]dist[i]=c[i]，并加入优先队列。其余计划的 dist[i]dist[i] 赋为极大值，并插入线段树。
  • 核心部分（主循环）：取出当前 distdist 数组中最小的计划 ii，查询可以衔接的计划 jj。
情况 11（t[i]≥t[j]t[i]\ge t[j]）：则在 LeftTree 中查询 l[j]−t[j]≤r[i]−t[i]l[j]-t[j]\leq r[i]-t[i] 的计划 jj。
情况 22（t[i]<t[j]t[i]<t[j]）：则在 RightTree 中查询 l[j]+t[j]≤r[i]+t[i]l[j]+t[j]\le r[i]+t[i] 的计划 jj。
对于所有查询到的 jj，检查 dist[j]>dist[i]+c[j]dist[j]>dist[i]+c[j]，如果是，则更新 dist[j]dist[j] 并加入优先队列，后从线段树中移除 jj（避免重复松弛）。

最终答案

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

AC Code

CPP
#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;
}
特别鸣谢：
  • 2011hym，
  • dizi_211，
  • ChenDaxiana。

评论

共 2 条评论，欢迎与作者交流。

正在加载评论...