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.
The first line contains two integers n and m (1 ≤ n, m ≤ 1, 000). The second line contains n distinct integers ai (1 ≤ ai ≤ 1, 000). The third line contains m distinct integers bi (1 ≤ bi ≤ 1, 000).
Print a non-negative integer denoting the minimum waiting time.
1 0
题意
有一个十字路口，分为东西方向和南北方向。两个方向在不同的时间点会有车辆经过，如果同一个时间点两个方向都有来车，就会发生交通事故，为了避免事故发生。于是规定，东西方向的车优先行驶，将南北方向的车辆的的通过时间向后推迟（整体推迟）
，求一个最小推迟时间使得东西方向与南北方向的车辆的通过时间点不会重叠。
题解
c数组记录东西方向通过的时间点（标记法），从0开始枚举推迟的时间t，d数组记录南北方向的通车情况，当有车通过的时间点数等于n+m，说明无重叠，当前时间即为所求
代码
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n,m,x,a[1005],b[1005];
while(~scanf("%d%d",&n,&m))
{
int c[2005]={0},d[2005]={0};
for(int i=1;i<=n;i++)
scanf("%d",&a[i]),c[a[i]]=1;
for(int i=1;i<=m;i++)
scanf("%d",&b[i]);
int time=-1;
while(1)
{
time++;
memset(d,0,sizeof(d));
for(int i=1;i<=m;i++)
{
d[b[i]+time]=1;
}
int sum=0;
for(int i=1;i<=2000;i++)
{
if(c[i]||d[i])
sum++;
}
if(sum==n+m)
break;
}
printf("%d\n",time);
}
}
View Code
