Codeforces Round 842 (Div. 2) B. Quick Sort
给一个长为 \(n\) 的排列 \(p\) 和一个正整数 \(k, (k \leq n)\) 。在一步操作中，可以：
- 选择 \(k\) 个不同的元素 \(p_{i_1}, p_{i_2}, \cdots, p_{i_k}\) 。
- 将他们移除然后排序，并拼接到剩余数组末尾
找到最小的操作数使得整个排列为增序。
典：将一个排列的一些数抽出来再加到原排列外侧使得有序。
- 重复抽出的数没有意义
- 证明：如果一个数被抽出一次以上，完全可以最后抽出。
- 存在一组序列（可能为 \(1\) ）最后不需要抽出。
- 证明：如果不存在这组序列，则所有元素都需要被抽出一遍，可以任意构造一种方法证明它是不存在的。
只需要一开始找出最长不需要被抽出的序列即可。
此处显然从 \(1\) 开始找连续递增段 \([1,2, \cdots, x]\) ，可以通过记录 \(pos_{p_i}\) 在线性复杂度做到。
于是则需要被抽出的数长度为 \(n - x\) ，又每次操作严格抽出 \(k\) 个，则最少操作次数为 \(\lceil \frac{n - x}{k} \rceil\) 。
view
#include <bits/stdc++.h>
void solve() {
int n, k; std::cin >> n >> k;
std::vector<int> a(n+1), pos(n+1);
for (int i = 1; i <= n; i++) std::cin >> a[i], pos[a[i]] = i;
int l = 1; while (l < n && pos[l+1] > pos[l]) l += 1;
std::cout << (n - l + k - 1) / k << '\n';
}
int main() {
int _ = 1; std::cin >> _;
while (_--) { solve(); }
return 0;
}