526互联

Codeforces Round 842 (Div. 2) B. Quick Sort

发布时间 2023-09-05 21:27:59作者: zsxuan

给一个长为 \(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;
}