Koxia and Permutation

题意翻译

Reve 有两个正整数 $n$，$k$。 对于一个由 $1$ 到 $n$ 的序列 $p$，有一个长为 $n - k + 1$ 的数列 $c$ 满足（其中 $i = 1, 2, \dots , n - k + 1$，所有的下标从 $1$ 开始)： $$c_i = \text{max}(p_i, p_{i + 1}, \dots , p_{i + k - 1}) + \text{min}(p_i, p_{i + 1}, \dots , p_{i + k - 1})$$ 称一个序列 $p$ 的*花费*为其对应的数列 $c$ 中的最大值。 现在请构造并输出一个由 $1$ 到 $n$ 的序列 $p$，使得该序列对应的*花费*最小。 一个由 $1$ 到 $n$ 的序列是正整数 $1, 2, \dots , n$ 的全排列。称 $[2, 3, 1, 5, 4]$ 是一个由 $1$ 到 $5$ 的序列，但 $[1, 2, 2]$ 不是一个由 $1$ 到 $2$ 的序列（ $2$ 出现了两次）；$[1, 3, 4]$ 不是一个由 $1$ 到 $3$ 的序列（ $4$ 出现了）。

题目描述

Reve has two integers $ n $ and $ k $ . Let $ p $ be a permutation $ ^\dagger $ of length $ n $ . Let $ c $ be an array of length $ n - k + 1 $ such that $ $c_i = \max(p_i, \dots, p_{i+k-1}) + \min(p_i, \dots, p_{i+k-1}). $ $ Let the <span class="tex-font-style-it">cost</span> of the permutation $ p $ be the maximum element of $ c $ .</p><p>Koxia wants you to construct a permutation with the minimum possible cost.</p><p> $ ^\\dagger $ A permutation of length $ n $ is an array consisting of $ n $ distinct integers from $ 1 $ to $ n $ in arbitrary order. For example, $ \[2,3,1,5,4\] $ is a permutation, but $ \[1,2,2\] $ is not a permutation ( $ 2 $ appears twice in the array), and $ \[1,3,4\] $ is also not a permutation ( $ n=3 $ but there is $ 4$ in the array).

输入输出格式

输入格式

Each test consists of multiple test cases. The first line contains a single integer $ t $ ( $ 1 \leq t \leq 2000 $ ) — the number of test cases. The description of test cases follows. The first line of each test case contains two integers $ n $ and $ k $ ( $ 1 \leq k \leq n \leq 2 \cdot 10^5 $ ). It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 2 \cdot 10^5 $ .

输出格式

For each test case, output $ n $ integers $ p_1,p_2,\dots,p_n $ , which is a permutation with minimal cost. If there is more than one permutation with minimal cost, you may output any of them.

输入输出样例

输入样例 #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

说明

In the first test case, - $ 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 $ . Therefore, the cost is $ \max(6,4,6)=6 $ . It can be proven that this is the minimal cost.

**题意翻译**

Reve有两个正整数 $n$ 和 $k$。对于一个由 $1$ 到 $n$ 的序列 $p$，有一个长为 $n - k + 1$ 的数列 $c$ 满足（其中 $i = 1, 2, \dots , n - k + 1$，所有的下标从 $1$ 开始）：

$$c_i = \text{max}(p_i, p_{i + 1}, \dots , p_{i + k - 1}) + \text{min}(p_i, p_{i + 1}, \dots , p_{i + k - 1})$$

称一个序列 $p$ 的*花费*为其对应的数列 $c$ 中的最大值。

现在请构造并输出一个由 $1$ 到 $n$ 的序列 $p$，使得该序列对应的*花费*最小。

一个由 $1$ 到 $n$ 的序列是正整数 $1, 2, \dots , n$ 的全排列。称 $[2, 3, 1, 5, 4]$ 是一个由 $1$ 到 $5$ 的序列，但 $[1, 2, 2]$ 不是一个由 $1$ 到 $2$ 的序列（ $2$ 出现了两次）；$[1, 3, 4]$ 不是一个由 $1$ 到 $3$ 的序列（ $4$ 出现了）。

**题目描述**

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

设 $p$ 为长度为 $n$ 的一个排列。设 $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想要你构造一个排列，使其具有最小的可能花费。

**输入输出格式**

**输入格式**

每个测试包含多个测试用例。第一行包含一个整数 $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$。可以证明这是最小的花费。**题意翻译** Reve有两个正整数 $n$ 和 $k$。对于一个由 $1$ 到 $n$ 的序列 $p$，有一个长为 $n - k + 1$ 的数列 $c$ 满足（其中 $i = 1, 2, \dots , n - k + 1$，所有的下标从 $1$ 开始）： $$c_i = \text{max}(p_i, p_{i + 1}, \dots , p_{i + k - 1}) + \text{min}(p_i, p_{i + 1}, \dots , p_{i + k - 1})$$ 称一个序列 $p$ 的*花费*为其对应的数列 $c$ 中的最大值。 现在请构造并输出一个由 $1$ 到 $n$ 的序列 $p$，使得该序列对应的*花费*最小。 一个由 $1$ 到 $n$ 的序列是正整数 $1, 2, \dots , n$ 的全排列。称 $[2, 3, 1, 5, 4]$ 是一个由 $1$ 到 $5$ 的序列，但 $[1, 2, 2]$ 不是一个由 $1$ 到 $2$ 的序列（ $2$ 出现了两次）；$[1, 3, 4]$ 不是一个由 $1$ 到 $3$ 的序列（ $4$ 出现了）。 **题目描述** Reve有两个整数 $n$ 和 $k$。 设 $p$ 为长度为 $n$ 的一个排列。设 $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想要你构造一个排列，使其具有最小的可能花费。 **输入输出格式** **输入格式** 每个测试包含多个测试用例。第一行包含一个整数 $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$。可以证明这是最小的花费。