自动搬运

查看原文

来自洛谷，原作者为

	Wsy_flying_forever Think three times,code twice and win the first place

搬运于2025-08-24 22:31:38，当前版本为作者最后更新于2022-01-19 22:42:57，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

看到这题的题解不是很多，我就来补一发。

题意简述

$n$ 个点移到 $n$ 个坑，一次全体移动一格，移到坑点就消失，求最小移动步数。

思路

初始坐标是无序的，我们先来将点与坑的坐标排个序再说（QAQ）
然后我们考虑这个点的移动情况。 对于每个点来说向左向右不断交替运动是没有任何意义的，我们应该让它往左或往右直接进坑，亦或是让它先向左或向右一小段距离满足其他点的需求，再一次性向右或向左进坑（如下图）
于是思路就产生了：
我们先用二分（尺取法也行）把每个节点和离他最近的左部坑之间的距离算出来，若左部无坑，则标为 $\infty$,右部点同理。这里要注意一点，我们需要把左部点距离与其编号捆绑在一起，便于求排序后其对应的右部点距离。将左部点距离进行排序后，依次枚举左部点，此时取该点为左移进坑点，由图得到 $d_1=2r_1+l_1$, 以该点为右部进坑点，由图得到$d_2=2l_2+r_2$,$ans$ 即可更新为 $\max(ans,d_1,d_2)$,输出答案即可。

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn=2e5+10;
typedef long long ll;
struct Node{
	ll l;
	int id;
	bool operator <(const Node &T)const{
		return l<=T.l;
	}
} t[maxn];
ll n,m,rmax,ans=1e16;
ll a[maxn],b[maxn],r[maxn];
inline ll read(){
	ll x=0,f=1;
	char ch=getchar();
	while (!isdigit(ch)){
	    if (ch=='-') f=-1;
	    ch=getchar();
	}
	while (isdigit(ch)){
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return x*f;
}
int main()
{
	n=read(),m=read();
	for (int i=1;i<=n;i++) a[i]=read();
	b[0]=-1e16;
	b[m+1]=1e16;
	for (int i=1;i<=m;i++) b[i]=read();
	sort(b+1,b+m+1);
	for (int i=1;i<=n;i++){
		t[i].l=a[i]-b[upper_bound(b+1,b+m+1,a[i])-b-1];
		t[i].id=i;
		r[i]=b[upper_bound(b+1,b+m+1,a[i])-b]-a[i];
    }
    sort(t+1,t+n+1);
    for (int i=n;i>=0;i--){
    	ans=min(ans,min(t[i].l*2+rmax,rmax*2+t[i].l));
    	rmax=max(r[t[i].id],rmax);
	}
	printf("%lld\n",ans);
	return 0;
}

写题解不易，点个赞再走吧！$Thank$ $you$