Үүрэн холбооны сүлжээ

3s

256MB

1500

0%

Binary SearchTwo Pointers

Шулуун дээр $n$ хот болон $m$ үүрэн холбооны цамхаг байрлана. Хотуудын $x$ координатууд нь $a_1, a_2, \dots, a_n$ , цамхгуудын $x$ координатууд нь $b_1, b_2, \dots, b_m$ байна.

Бүх цамхаг ижил зарчмаар ажиллана. Цамхаг өөрөөсөө $r$ -ээс ихгүй зайд байгаа хотуудыг сүлжээгээр хангана. Өөрөөр хэлбэл $i$ -р хотыг $j$ -р цамхаг хамарна гэдэг нь дараахтай адил:

$|a_i - b_j| \le r$

Хот бүр өөрт хамгийн ойр байгаа цамхагтайгаа $r$ -ээс ихгүй зайтай байхаар хамгийн бага $r$ -ийг ол.

Тэмдэглэл:

$r = 0$ бол цамхаг зөвхөн өөрийнх нь байрлаж буй цэгийг хамарна.
Нэг цамхаг хэдэн ч хотыг хамарч болно. Гэхдээ тэдгээр бүх хот цамхгаас $r$ -ээс ихгүй зайд байх ёстой.

Оролтын формат

Эхний мөрөнд хоёр натурал тоо $n$ ба $m$ байна ( $1 \le n, m \le 10^5$ ). Эдгээр нь хотын тоо, цамхгийн тоо юм.

Хоёр дахь мөрөнд $n$ бүхэл тоо $a_1, a_2, \dots, a_n$ байна ( $-10^9 \le a_i \le 10^9$ ). Эдгээр нь хотуудын координат юм. Нэг цэг дээр хэдэн ч хот байж болно. Бүх $a_i$ нь өсөхгүй биш (non-decreasing) дарааллаар өгөгдөнө.

Гурав дахь мөрөнд $m$ бүхэл тоо $b_1, b_2, \dots, b_m$ байна ( $-10^9 \le b_j \le 10^9$ ). Эдгээр нь цамхгуудын координат юм.

Гаралтын формат

Бүх хотыг сүлжээгээр хангах хамгийн бага $r$ -ийг хэвлэ.

Хязгаарлалт

$1 \le n, m \le 10^5$
$-10^9 \le a_i, b_j \le 10^9$
$a_i$ ба $b_j$ дараалалууд буурахгүй дарааллаар өгөгдсөн

Жишээ

Оролт1

3 2
-2 2 4
-3 0

Гаралт1

$4$ гэсэн хотыг хамгийн ойрын цамхаг болох $0$ координаттай цамхагаас $4$ зайд байна. Харин $-2$ болон $2$ гэсэн хотууд харгалзан $1$ , $2$ зайд байгаа тул хамгийн бага $r = 4$ болно.

Оролт2

5 3
1 5 10 14 17
4 11 15

Гаралт2

$1$ гэсэн хотыг хамгийн ойрын цамхаг болох $4$ координаттай цамхагаас $3$ зайд байна. Бусад хотууд харгалзан $1$ , $1$ , $1$ , $2$ зайд байгаа тул $r = 3$ хангалттай.

0.1 / 64 KiB

Редактор уншиж байна...