AcWing 3874. 三元组的最小距离
原题链接
中等
作者:
Misty.
,
2024-09-28 15:06:12
,
所有人可见
,
阅读 11
原来之前没弄明白,归并排序还是吊。
//自行证明 |a-b|+|a-c|+|b-c|=2*[max(a,b,c)-min(a,b,c)]
//边归并边做,比如abc三个序列,最小值为a,则b和c中就是临近的含有abc的区间,求下距离即可s=2*(max(b,c)-a)
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 100010;
int a[N],b[N],c[N];
LL res=1e18;
int main()
{
int l,m,n;
cin>>l>>m>>n;
for(int i=0;i<l;i++) cin>>a[i];
for(int i=0;i<m;i++) cin>>b[i];
for(int i=0;i<n;i++) cin>>c[i];
for(int i=0,j=0,k=0;i<l&&j<m&&k<n;)
{
int x=a[i],y=b[j],z=c[k];
res=min(res,(LL)(max(max(x,y),z))-min(min(x,y),z));
//最小的向前一步走
if(x<=y&&x<=z) i++;
else if(y<=x&&y<=z) j++;
else k++;
}
printf("%lld",res*2);
return 0;
}