题解

核心想法 将两组位置排序。用双指针遍历机台与“当前最近的传感器”。 对每个机台 $x$，沿着传感器指针从 $j$ 前进，只要传感器 $sensor[j+1]$ 更靠近 $x$（即满足 $|sensor[j+1]-x| \le |sensor[j]-x|$），就把 $j$ 加一。这样就能在线性时间内找到该机台到最近传感器的距离 $d=\min(|x-sensor[j]|,|x-sensor[j\pm1]|)$，把所有机台的最近距离的最大值作为答案。

正确性说明 机台位置递增时，离它最近的传感器指针不会后退： 若上一台机台的最近传感器是 $sensor[j]$，当机台移动到更右边的位置 $x'$ 时，$sensor[j-1]$ 不可能变得更近（两者都更远且 $sensor[j-1]$ 更劣），因此最近传感器的下标是单调不减的。于是一次从左到右扫描即可为每个机台找到最近传感器，最终答案就是

题目内容

在一条生产线上有$n$台机床，给定一个整数数组$machine,machine[1]$表示第$i$台机床的位置，$machine.size=n$;同时该产线上有$m$个烟雾告警器，给定一个数组$sensor，sensor$表示第$j$个告警器的位置，$sensor.size=m$;假设所有的告警器能检测的半径相同，请找出能覆盖所有机台的最小告警半径。

输入描述

第一行输入一个整数表示机台数量$n$;

第二行输入整形数组$machine$;

第三行输入一个整数表示告警器数量$m$;

第四行输入数组$sensor$

输出描述

输出一个正整数，表示可以覆盖所有机台的最小告警半径

样例1

输入

4
1 4 3 2
2 
3 5

输出

2

说明

在位置$[3,5]$上有$2$个告警器，需要告警半径为$2$，才能覆盖[1,2,3,4]所有位置上的机台

样例2

输入

3
1 2 3
1
2

输出

1

说明

在位置$[2]$上有一个告警器，如果告密半径为$1$，那么就可以覆盖$[1,2,3]$所有位置上的机台

提示

$0<machine[1],sensor[1]<=10^7$

$0<n,m<=10^5$