← 返回题目列表

Codeforces · 2098/B

B. 萨莎和公寓购买

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

Sasha 想在一条街道上购买一套公寓,该街道上的房屋从左到右编号为 $$$1$$$ 到 $$$10^9$$$。

这条街上有 $$$n$$$ 酒吧,位于编号为 $$$a_1、a_2、\ldots、a_n$$$ 的房屋内。请注意,同一栋房子里可能有多个酒吧,在这种情况下,这些酒吧被认为是不同的。

Sasha 担心,当他购买公寓时,一些酒吧可能会关门,但是 不超过 $$$k$$$ 柱可以关闭。

对于编号为 $$$x$$$ 的任何房屋,将 $$$f(x)$$$ 定义为所有打开的柱 $$$y$$$ 上 $$$|x - y|$$$ 的总和(即,关闭一些柱之后)。

当且仅当可以关闭最多 $$$k$$$ 条时,Sasha 才有可能购买编号为 $$$x$$$ 的房屋中的公寓(其中 $$$1 \le x \le 10^9$$$),以便之后 $$$f(x)$$$ 在所有房屋中变得最小。

确定 Sasha 可以购买多少套不同的房子。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \leq n \leq 10^5, 0 \leq k \lt n$$$) — 柱数和可以平仓的最大柱数。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) - 酒吧所在的门牌号。

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

输出

对于每个测试用例,输出一个整数 - Sasha 可以购买公寓的房屋数量。

示例

输入
复制

4
4 0
1 2 3 4
5 2
7 6 6 7 1
3 1
6 7 9
6 2
5 1 9 10 13 2

输出
复制

2
2
4
9

注意

在第一个测试用例中,没有一个酒吧可以关闭,因此只有编号为 $$$2$$$ 和 $$$3$$$ 的房屋适合。对于编号为 $$$2$$$ 的房子,距离总和为 $$$|2 - 1| + |2 - 2| + |2 - 3| + |2 - 4| = 4$$$,对于编号为 $$$3$$$ 的房子,距离之和为 $$$|3 - 1| + |3 - 2| + |3 - 3| + |3 - 4| = 4$$$。但是,对于编号为 $$$1$$$ 的房屋,距离总和将为 $$$|1 - 1| + |1 - 2| + |1 - 3| + |1 - 4| = 6$$$,所以编号为$$$1$$$的房子不适合。这也可以证明萨沙不能购买其他房子的公寓。

在第二个测试用例中,合适的房屋编号为 $$$6$$$ 和 $$$7$$$。对于萨莎来说,选择编号为 $$$6$$$ 的房子,只要没有一家酒吧关门就足够了。如果 Sasha 选择编号为 $$$7$$$ 的房屋,则 $$$1$$$ 和 $$$6$$$ 房屋中的酒吧可以关闭。然后,酒吧将位于编号为 $$$6$$$、$$$7$$$ 和 $$$7$$$ 的房屋中。