CF2018B Speedbreaker 题解

Super_Cube · 2024-10-05 17:37:13 · 题解

Solution

题意：初始区间为 [i,i]，时间为 1，每次可以将区间 [l,r] 扩展为 [l-1,r] 或 [l,r+1]，当 j\in[1,n]，都有扩展到 j 时的时间 \le a_j，则称 i 合法。求 1\sim n 的合法数。

贪心地想，每次肯定是往还没被扩展到且 a_i 最小的点进行扩展，这样一定不劣，因为若先去尝试拓展其他较大的 a_i 而导致这个点没有及时地更新到那就直接不合法了。

结论：若有解则答案必定为 (i-a_i,i+a_i) 的交集。

证明？首先不在交集内的点一定会存在至少一个城市无法到达。假设交集为 [l,r]，那么 \forall i\in[1,n],a_i\ge\max(i-l+1,r-i+1)（由交集定义推出），也就是说从 [l,r] 中任意点开始都是可以走完所有城市的。

判断无解的条件为 \exist t\in[1,n],\displaystyle\max_{a_i\le t} i-\min_{a_i\le t} i\ge t。怎么理解？对于所有时间不超过 t 的城市最坏情况就是卡点扩展完成，这个过程中一共就只能扩展 t 次，如果最大间隔是比 t 大的那一定扩展不完。

Code

#include<bits/stdc++.h>
int l[200005],r[200005];
int T,n,L,R,ans;
int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        L=0;R=n+1;
        for(int i=1;i<=n;++i)l[i]=0xfffff,r[i]=0;
        for(int i=1,x;i<=n;++i){
            scanf("%d",&x);
            L=std::max(L,std::max(1,i-x+1));
            R=std::min(R,std::min(i+x-1,n));
            if(l[x]==0xfffff)l[x]=i;r[x]=i;
        }
        for(int i=2;i<=n;++i)
            l[i]=std::min(l[i],l[i-1]),r[i]=std::max(r[i],r[i-1]);
        ans=0;
        for(int i=1;i<=n;++i)
            if(l[i]&&r[i]-l[i]+1>i)ans=-1,i=n;
        if(~ans)ans=R-L+1;
        if(ans<0)ans=0; 
        printf("%d\n",ans);
    }
    return 0;
}