hihoCoder 1514 : 偶像的条件（模拟+二分）

r囧r小猫 2024-02-17 21:56 7阅读 0赞

#### \#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

样例输出

思路：枚举其中一个班的学生，其他两个班采用二分找到最接近枚举的那个学生的身高。

AC代码：

#include<cstdio>
    #include<cstring>
    #include<cmath>
    #include<algorithm>
    using namespace std;
    #define INF 2000000000
    const int maxn=1e5+10;
    int A[maxn],B[maxn],C[maxn];
    int n,m,l;
    
    int binary_search(int *a,int x,int y,int t){
    	while(x<y){
          int m=x+(y-x)/2;
    	  if(a[m]>=t)y=m;
    	  else x=m+1;		
    	}
    	return x;
    }
    
    int main(){
    	while(scanf("%d%d%d",&n,&m,&l)==3){
    		for(int i=1;i<=n;i++)
    		scanf("%d",&A[i]);
    		
    		for(int i=1;i<=m;i++)
    		scanf("%d",&B[i]);
    		
    		for(int i=1;i<=l;i++)
    		scanf("%d",&C[i]);
    		
    		sort(B+1,B+m+1);
    		sort(C+1,C+l+1);
    		B[0]=C[0]=0;
    		
    		int Min=INF;
    		for(int i=1;i<=n;i++){
    			int index=binary_search(B,1,m,A[i]);
    		
    			int index2=binary_search(C,1,l,A[i]);
    			
    			Min=min(Min,abs(A[i]-B[index])+abs(A[i]-C[index2])+abs(B[index]-C[index2]));
    			if(index!=1)
    			Min=min(Min,abs(A[i]-B[index-1])+abs(A[i]-C[index2])+abs(B[index-1]-C[index2]));
    			if(index2!=1)
    			Min=min(Min,abs(A[i]-B[index])+abs(A[i]-C[index2-1])+abs(B[index]-C[index2-1]));
    			if(index!=1 && index2!=1)
    			Min=min(Min,abs(A[i]-B[index-1])+abs(A[i]-C[index2-1])+abs(B[index-1]-C[index2-1]));
    		}
    		
    		printf("%d\n",Min);
    	}
    	return 0;
    }