题解 33：P12845 [蓝桥杯 2025 国 A] 连锁反应

liu鲤鱼 · 2026-10-20 21:50:08 · 题解

前言

不知道在哪找到了这道题，题解区很多都是 SCC、线段树之类的解法。这里给出一种较为简单的解法。只需要掌握基本的贪心思维即可。

思路

首先按照坐标排序。

不难想到，炸弹的连锁爆炸会将数轴划分为若干个连续引爆区间。区间个数即为所求。

对于任意一个炸弹，我们想知道它在哪个区间，实际上就是想知道所有能连锁引爆它且离它最远的一个炸弹。不妨设 fal_i 表示第 i 个炸弹左侧能够引爆它的离它最远的炸弹。far_i 同理。

这个东西可以 O(n) 处理。维护一个“右侧最大引爆范围”，对于第 i 个炸弹，若其坐标在 i-1 号炸弹的区间的范围内，则用范围的右界更新它的右界，同时 fal_{i-1} \to fal_i；否则，意味着不能继续连锁爆炸，则它的右界自然成为新范围的右界。

左界同理。

这样就得到了 fal 和 far 两组数。然后从头到尾扫一遍即可。

排序 O(n \log n)，处理 O(n)。

代码

ll n,fal[N],far[N],ans,k;
struct node{
    ll p,l,r;
}a[N];
bool cmp(node x,node y){
    return x.p<y.p;
}
int main(){
    n=read();
    for(ll i=1;i<=n;i++){
        a[i].p=read();
        fal[i]=far[i]=i;
        a[i].l=a[i].p-read(),a[i].r=a[i].p+read();
        //得到其引爆范围
    }
    sort(a+1,a+n+1,cmp);
    for(ll i=2;i<=n;i++){
        if(a[i-1].r>=a[i].p){
            a[i].r=max(a[i].r,a[i-1].r);
            fal[i]=fal[i-1];
        }
        //处理 far[i]。为了方便直接把 a[i].r 更新为了区间的右界
    }
    for(ll i=n-1;i>0;i--){
        if(a[i+1].l<=a[i].p){
            a[i].l=min(a[i].l,a[i+1].l);
            far[i]=far[i+1];
        }
        //同理。
    }
    for(ll i=1;i<=n;i++){
        if(fal[i]>k){
            k=far[i];
            ans++;
        }
        //如果 fal[i]>k 说明不能连锁引爆到 i，新开一个区间。
    }
    write(ans);
    return 0;
}