#CS1076. 滑动窗口中位数

滑动窗口中位数

题目背景

翻译自 CSES-1076 题。

题目描述

给定一个包含 n 个整数的数组，任务是计算每个大小为 k 的滑动窗口的中位数，从左到右依次输出。

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

输入格式

第一行输入两个整数 n 和 k，分别代表数组的元素个数和滑动窗口的大小。

第二行输入 n 个整数 x1,x2,...,xnx_1, x_2, ..., x_nx1​,x2​,...,xn​，代表数组的值。

输出格式

输出 n−k+1n - k + 1n−k+1 个整数，表示每个滑动窗口的中位数。

样例

8 3
2 4 3 5 8 1 2 1

3 4 5 5 2 1

说明/提示

$1 \le k \leq n \le 2\cdot 10^5$

1≤xi≤1091 \leq x_i \le 10^91≤xi​≤109。