N. [海淀区小学组 2025] 蜂窝网络

A B C D E F G H I J K L M N O P Q R S T U V W X Y

Type: RemoteJudge

1000ms

512MiB

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

2025 年海淀区中小学生信息学竞赛小学组复赛题目，数据为洛谷自造。

题目描述

有 $n$ 个城市编号从 $1$ 到 $n$ 和 $m$ 个信号发射塔编号从 $1$ 到 $m$ 都分布在一条直线上，如果选择直线上某个点的坐标为 $0$ ，则这 $n$ 个城市的坐标可以描述为 $a_1, a_2, \dots, a_n$ ，这 $m$ 个信号发射塔的坐标可描述为 $b_1, b_2, \dots, b_m$ 。每个信号发射塔能为它左右不超过 $r$ 的距离以内的城市提供上网流量，你的任务是确定 $r$ 最小为多少时才能保证所有城市都有网络信号？

输入格式

第一行包含两个正整数 $n$ 和 $m$ ，分别表示城市的个数和信号发射塔的个数，第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ，依次为每个城市的位置坐标，第三行包含 $m$ 个整数 $b_1, b_2, \dots, b_m$ ，依次为每个信号发射塔的位置坐标。允许多个城市或信号发射塔位置相同。

输出格式

仅有一个整数，能使所有城市都有网络信号覆盖的最小的 $r$ 值。

3 2
-2 2 4
-3 0

5 3
1 5 10 14 17
4 11 15

提示

对于 $30\%$ 的数据， $1 \leq n, m \leq 500$ ，对于整数 $i, j$ ， $\forall i \in [1, n]$ ， $1 \leq a_i \leq 500$ ， $\forall j \in [1, m]$ ， $1 \leq b_j \leq 500$ 。
对于另外 $70\%$ 的数据， $1 \leq n, m \leq 10^5$ ，对于整数 $i, j$ ， $\forall i \in [1, n]$ ， $\forall j \in [1, m]$ ， $-10^9 \leq a_i, b_j \leq 10^9$ 。

2025-8 2025年CSP-J二分

Not Claimed

Status: Done
Problem: 25
Open Since: 2025-8-9 0:00
Deadline: 2025-8-24 23:59
Extension: 24 hour(s)