#1514 : 偶像的条件
时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
小Hi的学校正面临着废校的大危机。面对学校的危机，小Hi同学们决定从ABC三个班中各挑出一名同学成为偶像。
成为偶像团体的条件之一，就是3名团员之间的身高差越小越好。
已知ABC三个班同学的身高分别是A1..AN, B1..BM 和 C1..CL。请你从中选出3名同学Ai, Bj, Ck使得D=|Ai-Bj|+|Bj-Ck|+|Ck-Ai|最小。
输入
第一行包含3个整数，N, M和L。
第二行包含N个整数，A1, A2, ... AN。(1 <= Ai <= 100000000)
第三行包含M个整数，B1, B2, ... BM。(1 <= Bi <= 100000000)
第四行包含L个整数，C1, C2, ... CL。(1 <= Ci <= 100000000)
对于30%的数据, 1 <= N, M, L <= 100
对于60%的数据，1 <= N, M, L <= 1000
对于100%的数据，1 <= N, M, L <= 100000
输出
输出最小的D。
- 样例输入
3 3 3
170 180 190
195 185 175
180 160 200- 样例输出
10
#include<cmath>
#include<ctime>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e5+;
int n,m,l,a[N],b[N],c[N];
int ans=2e9;
inline int read(){
int x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
inline int ABS(int x){
return x>?x:-x;
}
int main(){
// freopen("sh.txt","r",stdin);
n=read();m=read();l=read();
for(int i=;i<=n;i++) a[i]=read();a[]=-1e9;a[n+]=1e9;
for(int i=;i<=m;i++) b[i]=read();b[]=-1e9;b[m+]=1e9;
for(int i=;i<=l;i++) c[i]=read();c[]=-1e9;c[l+]=1e9;
sort(a+,a+n+);
sort(b+,b+m+);
sort(c+,c+l+);
if(n<=){
for(int i=;i<=n;i++){
for(int j=;j<=m;j++){
for(int k=;k<=l;k++){
ans=min(ans,ABS(a[i]-b[j])+ABS(b[j]-c[k])+ABS(c[k]-a[i]));
}
}
}
}
else{
for(int i=,p1,p2,p3,p4;i<=n;i++){
p1=lower_bound(b+,b+m+,a[i])-b;
p2=upper_bound(b+,b+m+,a[i])-b;
if(ABS(b[p1])<1e9){
p3=lower_bound(c+,c+l+,a[i])-c;
p4=upper_bound(c+,b+l+,a[i])-c;
if(ABS(c[p3])<1e9) ans=min(ans,ABS(a[i]-b[p1])+ABS(b[p1]-c[p3])+ABS(c[p3]-a[i]));
if(ABS(c[p4])<1e9) ans=min(ans,ABS(a[i]-b[p1])+ABS(b[p1]-c[p4])+ABS(c[p4]-a[i]));
}
if(ABS(b[p2])<1e9){
p3=lower_bound(c+,c+l+,a[i])-c;
p4=upper_bound(c+,b+l+,a[i])-c;
if(ABS(c[p3])<1e9) ans=min(ans,ABS(a[i]-b[p2])+ABS(b[p2]-c[p3])+ABS(c[p3]-a[i]));
if(ABS(c[p4])<1e9) ans=min(ans,ABS(a[i]-b[p2])+ABS(b[p2]-c[p4])+ABS(c[p4]-a[i]));
}
}
}
printf("%d\n",ans);
return ;
}
70分代码（贪挂了）
//
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e5+;
int n,m,l,a[N],b[N],c[N];
int ans=2e9;
inline int read(){
int x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
inline int ABS(int x){
return x>?x:-x;
}
int main(){
n=read();m=read();l=read();
for(int i=;i<=n;i++) a[i]=read();
for(int i=;i<=m;i++) b[i]=read();
for(int i=;i<=l;i++) c[i]=read();
sort(a+,a+n+);
sort(b+,b+m+);
sort(c+,c+l+);
for(int i=,p1,p2,p3,p4;i<=n;i++){
p1=lower_bound(b+,b+m+,a[i])-b;
p2=lower_bound(c+,c+l+,a[i])-c;
for(int j=;j<;j++) for(int k=;k<;k++){
p3=p1-j;p4=p2-k;
if(p3<) p3++;if(p4<) p4++;
if(p3>m) p3--;if(p4>l) p4--;
ans=min(ans,ABS(a[i]-b[p3])+ABS(b[p3]-c[p4])+ABS(c[p4]-a[i]));
}
}
printf("%d\n",ans);
return ;
}