两数组最短距离
时间限制(普通/Java):1000MS/3000MS 运行内存限制:65536KByte
总提交:92 测试通过:62
描述
已知元素从小到大排列的两个数组x[]和y[]，请写出一个程序算出两个数组彼此之间差的绝对值中最小的一个，这叫做数组的距离。
输入
第一行为两个整数m, n(1≤m, n≤1000)，分别代表数组f[], g[]的长度。
第二行有m个元素，为数组f[]。
第三行有n个元素，为数组g[]。
输出
数组的最短距离
样例输入
5 5
1 2 3 4 5
6 7 8 9 10
样例输出
1
提示
你能想出O(n+m)的算法吗?^_^
加油!
题目来源
NUAA
分析：先排序然后交替上升。1msT_T！
#include <stdio.h>
#include <stdlib.h>
int Comp(const void *p1,const void *p2 )
{
return *((int *)p1) - *((int *)p2);
}
int main()
{
int m,n,*f,*g,i,j,_min=99999,temp;
scanf("%d%d",&m,&n);
f=new int [m];
g=new int [n];
for (i=0;i<m;i++)
{
scanf("%d",&f[i]);
}
for (i=0;i<n;i++)
{
scanf("%d",&g[i]);
}
qsort(f,m,sizeof(int),Comp);
qsort(g,n,sizeof(int),Comp);
for (i=0,j=0;i<m,j<n;)
{
temp=f[i]-g[j];
if (temp>0)
{
_min=_min<temp?_min:temp;
j++;
}
else if (temp<0)
{
temp*=-1;
_min=_min<temp?_min:temp;
i++;
}
else
{
_min=0;
break;
}
}
printf("%d\n",_min);
}