← 返回题目列表

Codeforces · 2048/B

B. 凯文和排列

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

Kevin 是排列相关问题的大师。你正在和凯文一起在黑森林散步,在你闲暇的时候,他想问你以下问题。

给定两个正整数 $$$ n $$$ 和 $$$ k $$$,构造一个长度为 $$$ n $$$ 的排列 $$$^{\text{∗}}$$$ $$$ p $$$,以最小化长度为 $$$ k $$$ 的所有子数组 $$$^{\text{†}}$$$ 的最小值之和。正式地,您需要最小化

$$$$$$ \sum_{i=1}^{n-k+1}\left(\min_{j=i}^{i+k-1} p_j\right)。 $$$$$$

输入

每个测试由多个测试用例组成。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^3$$$)。

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

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

输出

对于每个测试用例,在一行上输出 $$$ n $$$ 个整数 - 您构建的排列 $$$ p $$$。

如果有多个答案,您可以打印其中任何一个。

示例

输入 #1

3
4 2
6 1
8 3

输出 #1

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

注意

在第一个测试用例中,$$$ k=2 $$$,考虑长度为 $$$ 2 $$$ 的所有子数组:$$$ p_1,p_2 $$$ 的最小值为 $$$ 1 $$$,$$$ p_2,p_3 $$$ 的最小值为 $$$ 1 $$$,$$$ p_3,p_4 $$$ 的最小值为$$$ 2 $$$。总和 $$$ 1+1+2=4 $$$ 是所有可能排列中最小的。

在第二个测试用例中,长度 $$$ 1 $$$ 的所有子数组的最小值为 $$$ 5, 2, 1, 6, 4, 3 $$$,并且总和 $$$ 5+2+1+6+4+3=21 $$$ 被证明是最小的。