【Offer收割]编程练习赛15-题目1 : 偶像的条件】

本文主要是介绍【Offer收割]编程练习赛15-题目1 : 偶像的条件】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

【链接】：https://hihocoder.com/contest/offers15/problems
【题目描述】：
题目1 : 偶像的条件
时间限制: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
【思路】首先想到的是枚举第一个数组的元素，要使得满足差绝对值之和最小，那么就要在剩余数组中找到第一个大于等于第一个元素的位置，依次枚举，那么要不超时，自然用到STL的lower_bound()函数：
函数lower_bound()在first和last中的前闭后开区间进行二分查找,返回大于或等于val的第一个元素位置。
代码如下：

/***********************
[Offer收割]编程练习赛15     【A偶像的条件】
Author：herongwei
Time:2017/4/23 19:23
language：C++
http://blog.csdn.net/u013050857
***********************/
#pragma comment(linker,"/STACK:102400000,102400000")
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <set>
#include <stack>
#include <math.h>
#include <map>
#include <queue>
#include <deque>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long LL;
const int maxn = 1e5+10;
const LL MOD = 999999997;
const int inf= 0x3f3f3f3f;
int dir4[4][2]= {{1,0},{0,1},{-1,0},{0,-1}};
int dir8[8][2]= {{1,0},{1,1},{0,1},{-1,1},{-1,0},{-1,-1},{0,-1},{1,-1}};/*Super waigua */
#define INLINE __attribute__((optimize("O3"))) inline
INLINE char NC(void)
{static char buf[100000], *p1 = buf, *p2 = buf;if (p1 == p2){p2 = (p1 = buf) + fread(buf, 1, 100000, stdin);if (p1 == p2) return EOF;}return *p1++;
}INLINE void read(int &x)
{static char c;c = NC();int b = 1;for (x = 0; !(c >= '0' && c <= '9'); c = NC()) if(c == '-') b = -b;for (; c >= '0' && c <= '9'; x = x * 10 + c - '0', c = NC());x *= b;
}
int an[maxn];
int am[maxn];
int al[maxn];
int n,m,l;
int ret=inf;
void init()
{int x,y,s;for(int i=1; i<=n; ++i) read(an[i]);for(int i=1; i<=m; ++i) read(am[i]);for(int i=1; i<=l; ++i) read(al[i]);sort(an+1,an+n+1);sort(am+1,am+m+1);sort(al+1,al+l+1);
}
int solve(int an[],int am[],int al[],int nn,int mm,int ll)
{/*循环第一个数组*/for(int i=1; i<=nn; ++i){/*找到第一个大于等于an[i]的元素位置*/int tm=lower_bound(am+1,am+mm+1,an[i])-am;if(tm<=mm) /*一定要注意判断条件！*/{/*找到第一个大于等于am[tm]的元素位置*/int tl=lower_bound(al+1,al+ll+1,am[tm])-al;if(tl<=ll){ret=min(ret,abs(al[tl]-an[i])*2);}}}return ret;
}
int get_solve(int an[],int am[],int al[],int n,int m,int l)
{solve(an,am,al,n,m,l);solve(an,al,am,n,l,m);solve(am,an,al,m,n,l);solve(al,an,am,l,n,m);solve(am,al,an,m,n,l);solve(al,am,an,l,m,n);
}
int main()
{// freopen("in.txt","r",stdin);while(~scanf("%d %d %d",&n,&m,&l)){init();printf("%d\n",get_solve(an,am,al,n,m,l));}return 0;
}