← 返回题目列表

Codeforces · 1993/D

D. 医疗-imize

中文机器翻译题面 查看原题

给定两个正整数 $$$n$$$ 和 $$$k$$$,以及另一个 $$$n$$$ 整数数组 $$$a$$$。

在一次操作中,您可以选择 $$$a$$$ 中任意大小为 $$$k$$$ 的子数组,然后将其从数组中删除,而无需更改其他元素的顺序。更正式地说,令 $$$(l, r)$$$ 为对子数组 $$$a_l, a_{l+1}, \ldots, a_r$$$ 的操作,使得 $$$r-l+1=k$$$,那么执行此操作意味着将 $$$a$$$ 替换为 $$$[a_1, \ldots, a_{l-1}, a_{r+1}, \ldots, a_n]$$$。

例如,如果$$$a=[1,2,3,4,5]$$$,我们对该数组执行操作$$$(3,5)$$$,它将变成$$$a=[1,2]$$$。此外,操作$$$(2, 4)$$$导致$$$a=[1,5]$$$,操作$$$(1,3)$$$导致$$$a=[4,5]$$$。

当$$$a$$$的长度大于$$$k$$$时(这意味着$$$|a| \gt k$$$),您必须重复该操作。处理后数组 $$$a$$$ 中所有剩余元素的最大可能中位数 $$$^\dagger$$$ 是多少?

$$$^\dagger$$$长度为$$$n$$$的数组的中位数是我们对元素进行非降序排序后索引为$$$\left \lfloor (n+1)/2 \right \rfloor$$$的元素。例如:$$$median([2,1,5,4,3]) = 3$$$、$$$median([5]) = 5$$$ 和 $$$median([6,8,2,4]) = 4$$$。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le n, k \le 5 \cdot 10^5$$$)。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — 数组 $$$a$$$。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$5 \cdot 10^5$$$。

输出

对于每个测试用例,打印一个整数 - 执行操作后可能的最大中位数。

示例

输入 #1

5
4 3
3 9 9 2
5 3
3 2 5 6 4
7 1
5 9 2 6 5 4 6
8 2
7 1 2 6 8 3 4 5
4 5
3 4 5 6

输出 #1

3
4
9
6
4

注意

在第一个测试用例中,您可以选择一个子数组 $$$(l, r)$$$,它可以是 $$$(1, 3)$$$ 或 $$$(2, 4)$$$。因此,两个可获得的最终数组是$$$[3]$$$和$$$[2]$$$。前一个的中位数较大 ($$$3 > 2$$$),因此答案为 $$$3$$$。

在第二个测试用例中,可获得的三个最终数组是 $$$[6, 4]$$$、$$$[3, 4]$$$ 和 $$$[3, 2]$$$。它们的中位数分别为 $$$4$$$、$$$3$$$ 和 $$$2$$$。答案是$$$4$$$。

在第三个测试用例中,最终数组中只剩下一个元素,并且它可以是初始数组的任何元素。其中最大的是$$$9$$$,所以答案是$$$9$$$。