ACM 训练 数组的距离（单调性）----------C语言—菜鸟级
问题 1164: 【数组的距离】
时间限制: 1Sec 内存限制: 128MB 提交: 293 解决: 144
题目描述
已知元素从小到大排列的两个数组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
解题思路:将先第一数组储存起来 输入第二数组时 每输入一位输入 去与第一数组元素遍历找到 当前最优数组距离（优化：因为数组元素为单调递增所以距离的结果也为单调 如果当前处理与第一数组的元素大于前面处理过的则单调性破坏break跳出不用处理后面 后面的距离必然越来越大）
注意事项:
参考代码:
#include <stdio.h>
#include <stdlib.h>
long int abss(long int s)//绝对值
{
if(s<0)return -s;
else return s;
}
int main()
{
long int m,n,i,j,s,jl,ans,flag=0;
long int f[1001];
scanf("%ld%ld",&m,&n);
for(i=0;i<m;i++)
scanf("%ld",&f[i]);
for(i=0;i<n;i++)
{ scanf("%ld",&s);
if(!flag)
{ for(j=0;j<m;j++)
if(abss(s-f[j])<ans||j==0)ans=abss(s-f[j]);//求距离所以用绝对值
else break; //优化（单调性被破坏，上一个点位 极值点）
if(ans<jl||i==0)jl=ans;
if(jl==0||s>f[m-1])flag=1; //如果第二个数组的第一个（或任意）元素
//大于第一个数组的最后一个元素
} //那么距离就是只能jl=s-f[m-1] flag标记 后面不用处理
}
printf("%ld\n",jl);
return 0;
}
ACM 算法 文章被收录于专栏
分享一点经验和拙见
投递三维家等公司10个岗位