← 返回题目列表

Codeforces · 1770/B

B. Koxia 和排列

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

Reve 有两个整数 $$$n$$$ 和 $$$k$$$。

令 $$$p$$$ 为长度 $$$n$$$ 的排列 $$$^\dagger$$$。令 $$$c$$$ 为长度为 $$$n - k + 1$$$ 的数组,使得 $$$$$c_i = \max(p_i, \dots, p_{i+k-1}) + \min(p_i, \dots, p_{i+k-1})。$$$$$$ 令排列 $$$p$$$ 的成本为 $$$c$$$ 的最大元素。

Koxia 希望您以尽可能小的成本构造一个排列。

$$$^\dagger$$$ 长度 $$$n$$$ 的排列是一个数组,由 $$$n$$$ 不同的整数组成,从 $$$1$$$ 到 $$$n$$$ 的任意顺序。例如,$$$[2,3,1,5,4]$$$是一个排列,但$$$[1,2,2]$$$不是排列($$$2$$$在数组中出现两次),$$$[1,3,4]$$$也不是排列($$$n=3$$$但数组中有$$$4$$$)。

输入

每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 2000$$$) — 测试用例的数量。测试用例的描述如下。

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

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

输出

对于每个测试用例,输出 $$$n$$$ 整数 $$$p_1,p_2,\dots,p_n$$$,这是一个成本最小的排列。如果存在多个具有最小成本的排列,您可以输出其中任何一个。

示例

输入 #1

3
5 3
5 1
6 6

输出 #1

5 1 2 3 4
1 2 3 4 5
3 2 4 1 6 5

注意

在第一个测试用例中,

- $$$c_1 = \max(p_1,p_2,p_3) + \min(p_1,p_2,p_3) = 5 + 1 = 6$$$。
- $$$c_2 = \max(p_2,p_3,p_4) + \min(p_2,p_3,p_4) = 3 + 1 = 4$$$。
- $$$c_3 = \max(p_3,p_4,p_5) + \min(p_3,p_4,p_5) = 4 + 2 = 6$$$。

因此,成本为$$$\max(6,4,6)=6$$$。可以证明这是最小成本。