P7622 [AHOI2021初中组] 坑 题解
Wsy_flying_forever
·
·
题解
看到这题的题解不是很多，我就来补一发。
题意简述
### 思路
初始坐标是无序的，我们先来将点与坑的坐标排个序再说（QAQ）
然后我们考虑这个点的移动情况。
对于每个点来说向左向右不断交替运动是没有任何意义的，我们应该让它往左或往右直接进坑，亦或是让它先向左或向右一小段距离满足其他点的需求，再一次性向右或向左进坑（如下图）
[](https://imgtu.com/i/7c0WN9)
于是思路就产生了：
我们先用二分（尺取法也行）把每个节点和离他最近的左部坑之间的距离算出来，若左部无坑，则标为 $\infty$,右部点同理。这里要注意一点，我们需要把左部点距离与其编号捆绑在一起，便于求排序后其对应的右部点距离。将左部点距离进行排序后，依次枚举左部点，此时取该点为左移进坑点，由图得到 $d_1=2r_1+l_1$, 以该点为右部进坑点，由图得到$d_2=2l_2+r_2$,$ans$ 即可更新为 $\max(ans,d_1,d_2)$,输出答案即可。
### 代码
```cpp
#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