首页 > 代码库 > [Offer收割]编程练习赛15 A.偶像的条件[贪心]
[Offer收割]编程练习赛15 A.偶像的条件[贪心]
#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+5;int n,m,l,a[N],b[N],c[N];int ans=2e9;inline int read(){ int x=0,f=1;char ch=getchar(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} return x*f;}inline int ABS(int x){ return x>0?x:-x;}int main(){// freopen("sh.txt","r",stdin); n=read();m=read();l=read(); for(int i=1;i<=n;i++) a[i]=read();a[0]=-1e9;a[n+1]=1e9; for(int i=1;i<=m;i++) b[i]=read();b[0]=-1e9;b[m+1]=1e9; for(int i=1;i<=l;i++) c[i]=read();c[0]=-1e9;c[l+1]=1e9; sort(a+1,a+n+1); sort(b+1,b+m+1); sort(c+1,c+l+1); if(n<=100){ for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ for(int k=1;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=1,p1,p2,p3,p4;i<=n;i++){ p1=lower_bound(b+1,b+m+1,a[i])-b; p2=upper_bound(b+1,b+m+1,a[i])-b; if(ABS(b[p1])<1e9){ p3=lower_bound(c+1,c+l+1,a[i])-c; p4=upper_bound(c+1,b+l+1,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+1,c+l+1,a[i])-c; p4=upper_bound(c+1,b+l+1,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 0;}
//100#include<cstdio>#include<iostream>#include<algorithm>using namespace std;const int N=1e5+5;int n,m,l,a[N],b[N],c[N];int ans=2e9;inline int read(){ int x=0,f=1;char ch=getchar(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} return x*f;}inline int ABS(int x){ return x>0?x:-x;}int main(){ n=read();m=read();l=read(); for(int i=1;i<=n;i++) a[i]=read(); for(int i=1;i<=m;i++) b[i]=read(); for(int i=1;i<=l;i++) c[i]=read(); sort(a+1,a+n+1); sort(b+1,b+m+1); sort(c+1,c+l+1); for(int i=1,p1,p2,p3,p4;i<=n;i++){ p1=lower_bound(b+1,b+m+1,a[i])-b; p2=lower_bound(c+1,c+l+1,a[i])-c; for(int j=0;j<2;j++) for(int k=0;k<2;k++){ p3=p1-j;p4=p2-k; if(p3<1) p3++;if(p4<1) 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 0;}
[Offer收割]编程练习赛15 A.偶像的条件[贪心]
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。