Trung Vị Cửa Sổ Trượt

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Cho mảng $n$ phần tử. Với mỗi cửa sổ trượt kích thước $k$ , tìm trung vị (phần tử ở giữa khi sắp xếp). Nếu $k$ chẵn, chọn phần tử nhỏ hơn trong hai phần tử giữa.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên $n$ và $k$ .

Dòng thứ hai chứa $n$ số nguyên.

Dữ liệu ra

In ra $n - k + 1$ số nguyên: trung vị của mỗi cửa sổ.

Ràng buộc

$1 \leq k \leq n \leq 2 \times 10^{5}$
$1 \leq x_{i} \leq 10^{9}$

Ví dụ

Input	Output	Giải thích
8 3 2 4 3 5 8 1 2 1	3 4 5 5 2 1	[2,4,3]→3, [4,3,5]→4, [3,5,8]→5, ...

Bình luận

Không có bình luận tại thời điểm này.