CF1768B Quick Sort

给定一个长度为 $n$ 的排列 $p$ 和一个正整数 $k$，其中 $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}]$。 请你求出将排列按递增顺序排序所需的最少操作次数。可以证明总是可以做到。 $^\dagger$ 长度为 $n$ 的排列是由 $1$ 到 $n$ 的 $n$ 个不同整数组成的数组，顺序任意。例如，$[2,3,1,5,4]$ 是一个排列，但 $[1,2,2]$ 不是排列（$2$ 在数组中出现了两次），$[1,3,4]$ 也不是排列（$n=3$ 但数组中有 $4$）。

第一行包含一个整数 $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$。

对于每个测试用例，输出一个整数，表示将排列排序所需的最少操作次数。可以证明总是可以做到。

在第一个测试用例中，排列已经有序。 在第二个测试用例中，你可以选择元素 $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}]$。 在第四个测试用例中，可以证明无法通过一次操作将排列排序。但如果你第一次选择元素 $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}]$。 由 ChatGPT 4.1 翻译