P9342 [JOISC 2023 Day4] Bitaro's Travel 题解

· · 题解

题目

分析

看到题目首先会想到简单的暴力：

#include<iostream>
#include<cstdio>
#include<algorithm>
#define int long long
using std::cin;using std::cout;
constexpr int N=200005;
int n,a[N],q,s;
signed main(){
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
    cin>>n;
    for(int i=1;i<=n;++i) cin>>a[i];
    cin>>q;
    for(int i=1;i<=q;++i){
        cin>>s;
        int p=std::lower_bound(a+1,a+n+1,s)-a;//寻找最近点
        if(p==1) p=1;
        else if(p==n+1) p=n;
        else{
            if(a[p]-s<s-a[p-1]) p=p;
            else p=p-1;
        }
        int l=p-1,r=p+1,ans=std::abs(a[p]-s);
        while(p!=1&&p!=n){//暴力扩展两边
            if(a[p]-a[l]<=a[r]-a[p]) ans+=a[p]-a[l],p=l,--l;
            else ans+=a[r]-a[p],p=r,++r;
        }
        cout<<ans+a[n]-a[1]<<'\n';
    }
    return 0;
}

但是这个暴力是 O(qn) 的，显然过不去。

考虑优化这个暴力。

如果你对 a_p-a_l\le a_r-a_p 的结果输出一下的话，就会发现有很多 0 和 1 是连续出现的。

这实际上在提醒我们，Bitaro 的转向次数并不会很多。

考虑如果每走一次就要让他转向，那么他距离同向的下一个景点的距离一定大于他已经走过的距离，因为反向的下一个景点一定在上一个景点之后。

这样每次走过的路程将会以指数级增长，而路程总长只有 10^9，那么大约至多只有 31 次转向。

接下来继续想，在同向的连续段的行程中，如果后到达的点可以比其它点先被判到达，那么即使先到达的点未搜过，但是它一定可以比这个点先到达。

如果这个时候要转向，唯一的情况就是到前方最近的点的距离大于（或等于）后方的点的距离。这个时候我们假定可以往前走，走的路程为这个点到上一个转向点之后的点的距离（比如现在在 p，已经走过了 [l,r]，且 p=r，那么 l 一定为上一个转向点，(l-1) 为其之后的点）。这个时候我们往前搜，如果能搜到一个位置在这个距离以内，那么说明往前走会有更近的景点。反之就只能转向了。看到在有序数列中搜索一个位置，自然而然想到二分，而二分是 \log 级别的，复杂度在此得到了降低。

最后还可以优化的是，如果这个时候 Bitaro 已经走到 1 或 n 了，如果这个时候他还没走完，那么他一定会从 1 走到 n 或 从 n 走到 1 ，直接加上这段距离就可以了，不需要再次搜索。

这样子时间复杂度应该为 O(n+q\log n\log n)。一个 \log 是搜索，还有一个是与转向次数有关。

代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#define int long long
using std::cin;using std::cout;
constexpr int N=200005;
int n,a[N],q,s;
signed main(){
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
    cin>>n;
    for(int i=1;i<=n;++i) cin>>a[i];
    cin>>q;
    for(int i=1;i<=q;++i){
        cin>>s;
        int p=std::lower_bound(a+1,a+n+1,s)-a;//寻找最近点
        if(p==1) p=1;
        else if(p==n+1) p=n;
        else{
            if(a[p]-s<s-a[p-1]) p=p;
            else p=p-1;
        }
        int l=p,r=p;
        long long ans=std::abs(a[p]-s);
        while(l>1&&r<n){//触碰两端即可结束
            if(p==l){//优化扩展
                int dis=std::abs(a[p]-a[r+1]);
                int u=std::lower_bound(a+1,a+n+1,a[p]-dis)-a;
                if(u<l){//尝试继续往左扩展
                    ans+=std::abs(a[p]-a[u]);
                    p=l=u;
                }else{//不行则往右
                    ans+=dis;
                    p=++r;
                }
            }else{
                int dis=std::abs(a[p]-a[l-1]);
                int u=std::lower_bound(a+1,a+n+1,a[p]+dis)-a-1;//注意相等时左侧优先
                if(u>r){//尝试继续往右扩展
                    ans+=std::abs(a[u]-a[p]);
                    p=r=u;
                }else{//不行则往左
                    ans+=dis;
                    p=--l;
                }
            }
        }
        ans+=a[n]-a[1];
        cout<<ans<<'\n';
    }
    return 0;
}

最后感谢一下 @tyr 和 @lys 的教导！