链接: https://cses.fi/problemset/task/1076

板块: Sliding Window Problems

时限: 1.00 s ｜ 内存: 512 MB

题目描述

给定一个包含 $n$ 个整数的数组。你的任务是从左到右，计算每 $k$ 个元素组成的窗口的中位数。

中位数是指元素排序后位于中间的元素。如果元素个数为偶数，则有两个可能的中位数，我们约定中位数为其中较小的那个。

输入

第一行包含两个整数 $n$ 和 $k$：元素个数和窗口大小。

接下来有 $n$ 个整数 $x_1,x_2,\ldots,x_n$：数组的内容。

输出

输出 $n-k+1$ 个值：中位数。

数据范围

$1 \le k \le n \le 2 \cdot 10^5$ $1 \le x_i \le 10^9$

样例输入

8 3
2 4 3 5 8 1 2 1

样例输出

3 4 5 5 2 1