#ABC212C. 最小的差

最小的差

AT_abc212_c [ABC212C] Min Difference

题目描述

\hspace{15pt}给定两个正整数数列 a1,a2,…,ana_1,a_2,\dots,a_n 与 b1,b2,…,bmb_1,b_2,\dots,b_m。

\hspace{15pt}请你求出从每个数列中各选一个元素时,这两个值之差的最小值,即 $\min\limits_{1 \leqq i \leqq n}\min\limits_{1 \leqq j \leqq m}\left|a_i-b_j\right|$。

输入格式

\hspace{15pt}第一行输入两个整数 n,m(1≦n,m≦2×105)n,m \left(1 \leqq n,m \leqq 2 \times 10^5\right),代表两个数列的长度。

\hspace{15pt}第二行输入 nn 个整数 $a_1,a_2,\dots,a_n \left(1 \leqq a_i \leqq 10^9\right)$,代表数列 aa。

\hspace{15pt}第三行输入 mm 个整数 $b_1,b_2,\dots,b_m \left(1 \leqq b_j \leqq 10^9\right)$,代表数列 bb。

输出格式

\hspace{15pt}在一行上输出一个整数,代表 $\min\limits_{1 \leqq i \leqq n}\min\limits_{1 \leqq j \leqq m}\left|a_i-b_j\right|$。

测试样例

2 2
1 6
4 9
2

样例 1 解释

\hspace{15pt}在这个样例中,从每个数列中各选一个元素,两数之差可能为:

∙ \hspace{23pt}\bullet\, ∣a1−b1∣=∣1−4∣=3\left|a_1-b_1\right|=\left|1-4\right|=3;

∙ \hspace{23pt}\bullet\, ∣a1−b2∣=∣1−9∣=8\left|a_1-b_2\right|=\left|1-9\right|=8;

∙ \hspace{23pt}\bullet\, ∣a2−b1∣=∣6−4∣=2\left|a_2-b_1\right|=\left|6-4\right|=2;

∙ \hspace{23pt}\bullet\, ∣a2−b2∣=∣6−9∣=3\left|a_2-b_2\right|=\left|6-9\right|=3。

\hspace{15pt}共 44 种情况,其中最小值为 22,因此输出 22。

1 1
10
10
0
6 8
82 76 82 82 71 70
17 39 67 2 45 35 22 24
3