[海淀区小学组 2024] 蜂窝网络

Luogu

IDLGB4242

Time1000ms

Memory512MB

DifficultyP3

二分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$ 最小为多少时才能保证所有城市都有网络信号？ ## Input 第一行包含两个正整数 $n$ 和 $m$，分别表示城市的个数和信号发射塔的个数，第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$，依次为每个城市的位置坐标，第三行包含 $m$ 个整数 $b_1, b_2, \dots, b_m$，依次为每个信号发射塔的位置坐标。允许多个城市或信号发射塔位置相同。 ## Output 仅有一个整数，能使所有城市都有网络信号覆盖的最小的 $r$ 值。 [samples] ## Background 2024 年海淀区中小学生信息学竞赛小学组复赛题目，数据为洛谷自造。 ## Note - 对于 $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$。

Samples

Input #1

3 2
-2 2 4
-3 0

Output #1

Input #2

5 3
1 5 10 14 17
4 11 15

Output #2

API Response (JSON)

{
  "problem": {
    "name": "[海淀区小学组 2024] 蜂窝网络",
    "description": {
      "content": "有 $n$ 个城市编号从 $1$ 到 $n$ 和 $m$ 个信号发射塔编号从 $1$ 到 $m$ 都分布在一条直线上，如果选择直线上某个点的坐标为 $0$，则这 $n$ 个城市的坐标可以描述为 $a_1, a_2, \\dots, a_n$，这 $m$ 个信号发射塔的坐标可描述为 $b_1, b_2, \\dots, b_m$。每个信号发射塔能为它左右不超过 $r$ 的距离以内的城市提供上网流量，你的",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P3"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGB4242"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "有 $n$ 个城市编号从 $1$ 到 $n$ 和 $m$ 个信号发射塔编号从 $1$ 到 $m$ 都分布在一条直线上，如果选择直线上某个点的坐标为 $0$，则这 $n$ 个城市的坐标可以描述为 $a_1, a_2, \\dots, a_n$，这 $m$ 个信号发射塔的坐标可描述为 $b_1, b_2, \\dots, b_m$。每个信号发射塔能为它左右不超过 $r$ 的距离以内的城市提供上网流量，你的...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments