题解

核心想法 将两组位置排序。用双指针遍历机台与“当前最近的传感器”。 对每个机台 $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]$ 更劣），因此最近传感器的下标是单调不减的。于是一次从左到右扫描即可为每个机台找到最近传感器，最终答案就是 $R$=$\max\limits_{x\in machine}$$\ \min\limits_{y\in sensor}|x-y|$。

C++

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) return 0;
    vector<long long> machine(n);
    for (int i = 0; i < n; ++i) cin >> machine[i];

    int m;
    cin >> m;
    vector<long long> sensor(m);
    for (int i = 0; i < m; ++i) cin >> sensor[i];

    // 排序两组位置
    sort(machine.begin(), machine.end());
    sort(sensor.begin(), sensor.end());

    // 双指针：j 指向当前最可能最近的传感器
    long long ans = 0;
    int j = 0;
    for (long long x : machine) {
        // 只要右侧传感器更近，就右移 j
        while (j + 1 < m && llabs(sensor[j + 1] - x) <= llabs(sensor[j] - x)) {
            ++j;
        }
        ans = max(ans, llabs(sensor[j] - x)); // 更新最小所需半径
    }

    cout << ans << "\n";
    return 0;
}

Python

import sys

def main():
    data = list(map(int, sys.stdin.read().strip().split()))
    if not data:
        return
    it = iter(data)
    n = next(it)
    machines = [next(it) for _ in range(n)]
    m = next(it)
    sensors = [next(it) for _ in range(m)]

    # 排序
    machines.sort()
    sensors.sort()

    # 双指针
    j = 0
    ans = 0
    for x in machines:
        # 右侧更近就前进
        while j + 1 < m and abs(sensors[j + 1] - x) <= abs(sensors[j] - x):
            j += 1
        ans = max(ans, abs(sensors[j] - x))

    print(ans)

if __name__ == "__main__":
    main()

Java

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        ArrayList<Integer> vals = new ArrayList<>();
        String line;
        while ((line = br.readLine()) != null) {
            line = line.trim();
            if (line.isEmpty()) continue;
            String[] parts = line.split("\\s+");
            for (String p : parts) vals.add(Integer.parseInt(p));
        }
        if (vals.isEmpty()) return;

        int idx = 0;
        int n = vals.get(idx++);
        long[] machines = new long[n];
        for (int i = 0; i < n; i++) machines[i] = vals.get(idx++);

        int m = vals.get(idx++);
        long[] sensors = new long[m];
        for (int i = 0; i < m; i++) sensors[i] = vals.get(idx++);

        Arrays.sort(machines);
        Arrays.sort(sensors);

        // 双指针
        int j = 0;
        long ans = 0;
        for (long x : machines) {
            while (j + 1 < m && Math.abs(sensors[j + 1] - x) <= Math.abs(sensors[j] - x)) {
                j++;
            }
            ans = Math.max(ans, Math.abs(sensors[j] - x));
        }

        System.out.println(ans);
    }
}

题目内容

在一条生产线上有$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$