Гулгуур цонхны медиана

2s

512MB

1910

0%

Sliding Window Problems

$n$ бүхэл тоо бүхий массив өгөгдсөн. Зүүнээс баруун тийш $k$ элемент бүхий цонх бүрийн медианыг ол.

Медиана бол элементүүдийг эрэмбэлбэл гарч ирэх дунд элемент. Элементийн тоо тэгш бол хоёр медиана боломжтой — багийг нь авна.

Эх сурвалж: cses.fi

Эхний мөрөнд хоёр бүхэл тоо $n$ ба $k$ байна: элементийн тоо ба цонхны хэмжээ.

Дараа нь $n$ бүхэл тоо $x_1,x_2,\ldots,x_n$ байна: массивын утгууд.

$n-k+1$ утга хэвлэ: медианууд.

Оролт1

8 3
2 4 3 5 8 1 2 1

Гаралт1

3 4 5 5 2 1

0.1 / 64 KiB

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