Quick Sort

题意翻译

给你一个长度为 $n$ 的排列 $^\dagger$ $p$ 和一个正整数 $k \le n$。 在一次操作中，你要 - 选择 $ k $ 个不同的元素 $p_{i_1}, p_{i_2}, \ldots, p_{i_k}$。 - 从排列中移除它们，然后将它们按照递增的顺序添加到排列的末尾。 例如，如果 $p=[2,5,1,3,4],k=2$，你选择 $5$ 和 $3$ 作为操作的元素，那么 $[2,\color{red}{5}\color{black}{,1,}\ \color{red}{3}\color{black}{,4}] \rightarrow [2,1,4,\color{red}{3},\color{red}{5}\color{black}]$。 找出将这个排列按递增顺序排序所需的最少操作数。可以证明，总是可以这样做的。 $^\dagger$ 一个长度为 $n$ 的排列是一个由 $1$ 到 $n$ 的不同整数按任意顺序组成的数列。例如，$[2,3,1,5,4]$ 是一个排列，但 $[1,2,2]$ 不是排列（$2$ 在数列中出现两次），$[1,3,4]$ 也不是排列（$n=3$ 但在数列中有 $4$）。

题目描述

You are given a permutation $ ^\dagger $ $ p $ of length $ n $ and a positive integer $ k \le n $ . In one operation, you: - Choose $ k $ distinct elements $ p_{i_1}, p_{i_2}, \ldots, p_{i_k} $ . - Remove them and then add them sorted in increasing order to the end of the permutation. For example, if $ p = [2,5,1,3,4] $ and $ k = 2 $ and you choose $ 5 $ and $ 3 $ as the elements for the operation, then $ [2, \color{red}{5}, 1, \color{red}{3}, 4] \rightarrow [2, 1, 4, \color{red}{3},\color{red}{5}] $ . Find the minimum number of operations needed to sort the permutation in increasing order. It can be proven that it is always possible to do so. $ ^\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).

输入输出格式

输入格式

The first line contains a single integer $ t $ ( $ 1 \le t \le 10^4 $ ) — the number of test cases. The description of test cases follows. The first line of each test case contains two integers $ n $ and $ k $ ( $ 2 \le n \le 10^5 $ , $ 1 \le k \le n $ ). The second line of each test case contains $ n $ integers $ p_1,p_2,\ldots, p_n $ ( $ 1 \le p_i \le n $ ). It is guaranteed that $ p $ is a permutation. It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 10^5 $ .

输出格式

For each test case output a single integer — the minimum number of operations needed to sort the permutation. It can be proven that it is always possible to do so.

输入输出样例

输入样例 #1

4
3 2
1 2 3
3 1
3 1 2
4 2
1 3 2 4
4 2
2 3 1 4

输出样例 #1

0
1
1
2

说明

In the first test case, the permutation is already sorted. In the second test case, you can choose element $ 3 $ , and the permutation will become sorted as follows: $ [\color{red}{3}, 1, 2] \rightarrow [1, 2, \color{red}{3}] $ . In the third test case, you can choose elements $ 3 $ and $ 4 $ , and the permutation will become sorted as follows: $ [1, \color{red}{3}, 2, \color{red}{4}] \rightarrow [1, 2, \color{red}{3},\color{red}{4}] $ . In the fourth test case, it can be shown that it is impossible to sort the permutation in $ 1 $ operation. However, if you choose elements $ 2 $ and $ 1 $ in the first operation, and choose elements $ 3 $ and $ 4 $ in the second operation, the permutation will become sorted as follows: $ [\color{red}{2}, 3, \color{red}{1}, 4] \rightarrow [\color{blue}{3}, \color{blue}{4}, \color{red}{1}, \color{red}{2}] \rightarrow [1,2, \color{blue}{3}, \color{blue}{4}] $ .

**快速排序**

**题意翻译**
给你一个长度为 $ n $ 的排列 $ p $ 和一个正整数 $ k \le n $。

在一次操作中，你要：

- 选择 $ k $ 个不同的元素 $ p_{i_1}, p_{i_2}, \ldots, p_{i_k} $。
- 从排列中移除它们，然后将它们按照递增的顺序添加到排列的末尾。

例如，如果 $ p=[2,5,1,3,4],k=2 $，你选择 $ 5 $ 和 $ 3 $ 作为操作的元素，那么 $ [2,\color{red}{5}\color{black}{,1,}\ \color{red}{3}\color{black}{,4}] \rightarrow [2,1,4,\color{red}{3},\color{red}{5}\color{black}] $。

找出将这个排列按递增顺序排序所需的最少操作数。可以证明，总是可以这样做的。

**题目描述**
给定一个长度为 $ n $ 的排列 $ p $ 和一个正整数 $ k \le n $。

在一次操作中，你：

- 选择 $ k $ 个不同的元素 $ p_{i_1}, p_{i_2}, \ldots, p_{i_k} $。
- 移除它们，然后按递增顺序将它们添加到排列的末尾。

例如，如果 $ p = [2,5,1,3,4] $ 和 $ k = 2 $ 并且你选择 $ 5 $ 和 $ 3 $ 作为操作的元素，那么 $ [2, \color{red}{5}, 1, \color{red}{3}, 4] \rightarrow [2, 1, 4, \color{red}{3},\color{red}{5}] $。

找出将排列按递增顺序排序所需的最少操作数。可以证明，总是可以这样做的。

**输入输出格式**

**输入格式**
第一行包含一个整数 $ t $（$ 1 \le t \le 10^4 $）——测试用例的数量。接下来是每个测试用例的描述。

每个测试用例的第一行包含两个整数 $ n $ 和 $ k $（$ 2 \le n \le 10^5 $，$ 1 \le k \le n $）。

每个测试用例的第二行包含 $ n $ 个整数 $ p_1,p_2,\ldots, p_n $（$ 1 \le p_i \le n $）。保证 $ p $ 是一个排列。

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

**输出格式**
对于每个测试用例输出一个整数——将排列按递增顺序排序所需的最少操作数。可以证明，总是可以这样做的。

**输入输出样例**

**输入样例 #1**
```
4
3 2
1 2 3
3 1
3 1 2
4 2
1 3 2 4
4 2
2 3 1 4
```

**输出样例 #1**
```
0
1
1
2
```

**说明**
在第一个测试用例中，排列已经排序。

在第二个测试用例中，你可以选择元素 $ 3 $，排列将按如下方式排序：$ [\color{red}{3}, 1, 2] \rightarrow [1, 2, \color{red}{3}] $。

在第三个测试用例中，你可以选择元素 $ 3 $ 和 $ 4 $，排列将按如下方式排序：$ [1, \color{red}{3}, 2, \color{red}{4}] \rightarrow [1, 2, \color{red}{3},\color{red}{4}] $。

在第四个测试用例中，可以证明无法在 $ 1 $ 次操作内排序。但是，如果你在第一次操作中选择元素 $ 2 $ 和 $ 1 $，在第二次操作中选择元素 $ 3 $ 和 $ 4 $，排列将按如下方式排序：$ [\color{red}{2}, 3, \color{red}{1}, 4] \rightarrow [\color{blue}{3}, \color{blue}{4}, \color{red}{1}, \color{red}{2}] \rightarrow [1,2, \color{blue}{3}, \color{blue}{4}] $。**快速排序** **题意翻译** 给你一个长度为 $ n $ 的排列 $ p $ 和一个正整数 $ k \le n $。 在一次操作中，你要： - 选择 $ k $ 个不同的元素 $ p_{i_1}, p_{i_2}, \ldots, p_{i_k} $。 - 从排列中移除它们，然后将它们按照递增的顺序添加到排列的末尾。 例如，如果 $ p=[2,5,1,3,4],k=2 $，你选择 $ 5 $ 和 $ 3 $ 作为操作的元素，那么 $ [2,\color{red}{5}\color{black}{,1,}\ \color{red}{3}\color{black}{,4}] \rightarrow [2,1,4,\color{red}{3},\color{red}{5}\color{black}] $。 找出将这个排列按递增顺序排序所需的最少操作数。可以证明，总是可以这样做的。 **题目描述** 给定一个长度为 $ n $ 的排列 $ p $ 和一个正整数 $ k \le n $。 在一次操作中，你： - 选择 $ k $ 个不同的元素 $ p_{i_1}, p_{i_2}, \ldots, p_{i_k} $。 - 移除它们，然后按递增顺序将它们添加到排列的末尾。 例如，如果 $ p = [2,5,1,3,4] $ 和 $ k = 2 $ 并且你选择 $ 5 $ 和 $ 3 $ 作为操作的元素，那么 $ [2, \color{red}{5}, 1, \color{red}{3}, 4] \rightarrow [2, 1, 4, \color{red}{3},\color{red}{5}] $。 找出将排列按递增顺序排序所需的最少操作数。可以证明，总是可以这样做的。 **输入输出格式** **输入格式** 第一行包含一个整数 $ t $（$ 1 \le t \le 10^4 $）——测试用例的数量。接下来是每个测试用例的描述。 每个测试用例的第一行包含两个整数 $ n $ 和 $ k $（$ 2 \le n \le 10^5 $，$ 1 \le k \le n $）。 每个测试用例的第二行包含 $ n $ 个整数 $ p_1,p_2,\ldots, p_n $（$ 1 \le p_i \le n $）。保证 $ p $ 是一个排列。 保证所有测试用例的 $ n $ 之和不超过 $ 10^5 $。 **输出格式** 对于每个测试用例输出一个整数——将排列按递增顺序排序所需的最少操作数。可以证明，总是可以这样做的。 **输入输出样例** **输入样例 #1** ``` 4 3 2 1 2 3 3 1 3 1 2 4 2 1 3 2 4 4 2 2 3 1 4 ``` **输出样例 #1** ``` 0 1 1 2 ``` **说明** 在第一个测试用例中，排列已经排序。 在第二个测试用例中，你可以选择元素 $ 3 $，排列将按如下方式排序：$ [\color{red}{3}, 1, 2] \rightarrow [1, 2, \color{red}{3}] $。 在第三个测试用例中，你可以选择元素 $ 3 $ 和 $ 4 $，排列将按如下方式排序：$ [1, \color{red}{3}, 2, \color{red}{4}] \rightarrow [1, 2, \color{red}{3},\color{red}{4}] $。 在第四个测试用例中，可以证明无法在 $ 1 $ 次操作内排序。但是，如果你在第一次操作中选择元素 $ 2 $ 和 $ 1 $，在第二次操作中选择元素 $ 3 $ 和 $ 4 $，排列将按如下方式排序：$ [\color{red}{2}, 3, \color{red}{1}, 4] \rightarrow [\color{blue}{3}, \color{blue}{4}, \color{red}{1}, \color{red}{2}] \rightarrow [1,2, \color{blue}{3}, \color{blue}{4}] $。