JXCPC 1007

2019-07-21

这是要点思维的签到模拟题

Traffic

Problem Description

Avin is observing the cars at a crossroads. He finds that there are n cars running in the east-west direction with the i-th car passing the intersection at time ai . There are another m cars running in the north-south direction with the i-th car passing the intersection at time bi . If two cars passing the intersections at the same time, a traffic crash occurs. In order to achieve world peace and harmony, all the cars running in the north-south direction wait the same amount of integral time so that no two cars bump. You are asked the minimum waiting time.

Input

The first line contains two integers $n$ and $m (1 \leq n, m \leq 1, 000)$. The second line contains $n$ distinct integers $a_i (1 \leq ai \leq 1, 000)$. The third line contains $m$ distinct integers $b_i (1 \leq b_i \leq 1, 000)$.

Output

Print a non-negative integer denoting the minimum waiting time.

Sample Input

1 1
1
1
1 2
2
1 3

Sample Output

1
0

The Code Of My Program

/*********************
*@Author:   ChenShou *
*@Language: C++11    *
*********************/
//#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:102400000,102400000")
#include<functional>
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<sstream>
#include<iomanip>
#include<numeric>
#include<cctype>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>

//#define DEBUG
#define RI register int
#define endl "\n"

using namespace std;
typedef long long ll;
//typedef __int128 lll;
//const int N=100000+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-9;
const int INF = 0x3f3f3f3f;

inline long long read(){
    long long 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<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}

int main()
{
#ifdef DEBUG
    freopen("input.in", "r", stdin);
    //freopen("output.out", "w", stdout);
#endif
    //cout.tie(0);
    //scanf("%d",&t);
    //while(t--){
    //}
    bool a[3005];int b[2005];
	int n,m;
	while(scanf("%d %d",&n,&m)!=EOF)
	{
		int k;
		memset(a,0,sizeof(a));memset(b,0,sizeof(b));
		for(int i=0;i<n;i++) {scanf("%d",&k);  a[k]=true;}//将东西向的车通过的时间标记下来
		for(int i=0;i<m;i++) scanf("%d",&b[i]);//输入南北向车的时间
		for(int i=0; ;i++)
		{
			int f=0;
			for(int j=0;j<m;j++)//判断是不是南北向所有的车在等待 t 时间后都不会和东西向的车相撞
			{
				if(a[b[j]+i]==true)//相撞
				{
					f=1;break;
				}
			}
			if(f==0)//都没有相撞，满足条件，输出最小的等待时间
			{				
				cout<<i<<endl;break;
			}
		}
	}
#ifdef DEBUG
    printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
    //cout << "Fuck You !" << endl;
    return 0;
}