题解
核心想法
将两组位置排序。用双指针遍历机台与“当前最近的传感器”。
对每个机台 x，沿着传感器指针从 j 前进，只要传感器 sensor[j+1] 更靠近 x（即满足 ∣sensor[j+1]−x∣≤∣sensor[j]−x∣），就把 j 加一。这样就能在线性时间内找到该机台到最近传感器的距离 d=min(∣x−sensor[j]∣,∣x−sensor[j±1]∣)，把所有机台的最近距离的最大值作为答案。
正确性说明
机台位置递增时，离它最近的传感器指针不会后退：
若上一台机台的最近传感器是 sensor[j]，当机台移动到更右边的位置 x′ 时，sensor[j−1] 不可能变得更近（两者都更远且 sensor[j−1] 更劣），因此最近传感器的下标是单调不减的。于是一次从左到右扫描即可为每个机台找到最近传感器，最终答案就是
P3741.第2题-求告警器的最小告警半径
题目内容
在一条生产线上有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]<=107
0<n,m<=105
