分数: 300 点
问题陈述
给你两个序列: A=(A_1,A_2, \ldots ,A_N) 组成 N 正整数,以及 B=(B_1, \ldots ,B_M) 组成 M 正整数。
找到以下元素的最小差异 A 和一个元素 B,即 \displaystyle \min_{ 1\leq i\leq N}\displaystyle\min_{1\leq j\leq M} \lvert A_i-B_j\rvert.
约束
- 1 \leq N,M \leq 2\times 10^5
- 1 \leq A_i \leq 10^9
- 1 \leq B_i \leq 10^9
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N M A_1 A_2 \ldots A_N B_1 B_2 \ldots B_M
输出
打印答案。
示例输入 1
2 2 1 6 4 9
示例输出 1
2
这是四对元素中每一对的差异 A 和一个元素 B: \lvert 1-4\rvert=3, \lvert 1-9\rvert=8, \lvert 6-4\rvert=2,和 \lvert 6-9\rvert=3。我们应该打印这些值中的最小值,或者 2.
示例输入 2
1 1 10 10
示例输出 2
0
示例输入 3
6 8 82 76 82 82 71 70 17 39 67 2 45 35 22 24
示例输出 3
3