自动搬运

查看原文

来自洛谷，原作者为

	Cure_Wing 我想：希望是本无所谓有，无所谓无的。这正如地上的路；其实地上本没有路，走的人多了，也便成了路。

搬运于2025-08-24 22:47:30，当前版本为作者最后更新于2023-07-13 08:13:41，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目

分析

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

#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 的教导！