A1760 | 新年排列
时间限制1s
内存限制128MB
通过 / 提交0/0
题目描述
有一个长度为 $n$ 的新年排列 $p$，还有一个神秘的整数 $k$。
排列 $p$ 中的每个元素 $p_i$ 满足 $1 \leq p_i \leq n$，并且排列 $p$ 中的元素不会重复。
现在，你可以任意多次执行以下操作：每次选择 $k$ 个元素，将选择的元素 从小到大排序 后移动到 $p$ 的尾部。例如，当 $n = 4$，$k = 2$，$p = [1,4,3,2]$ 时，你可以选择 $4$ 和 $3$ 排序后移动到 $p$ 的尾部，使得 $p = [1,2,3,4]$。这样的操作一次就能让 $p$ 变成升序排列。
求将排列 $p$ 变成升序的操作最小次数。祝你在这个新年排序挑战中获得成功！
排列 $p$ 中的每个元素 $p_i$ 满足 $1 \leq p_i \leq n$，并且排列 $p$ 中的元素不会重复。
现在，你可以任意多次执行以下操作：每次选择 $k$ 个元素，将选择的元素 从小到大排序 后移动到 $p$ 的尾部。例如，当 $n = 4$，$k = 2$，$p = [1,4,3,2]$ 时，你可以选择 $4$ 和 $3$ 排序后移动到 $p$ 的尾部，使得 $p = [1,2,3,4]$。这样的操作一次就能让 $p$ 变成升序排列。
求将排列 $p$ 变成升序的操作最小次数。祝你在这个新年排序挑战中获得成功！
输入格式
第一行输入一个 $n(2 \leq n \leq 10^5)$ 和 $k(1 \leq k \leq n)$,表示总共有 $n$ 个整数，每次操作会选择 $k$ 个数。
第二行输入 $n$ 个整数 $p_1,p_2,\ldots, p_n(1 \le p_i \le n$)。
第二行输入 $n$ 个整数 $p_1,p_2,\ldots, p_n(1 \le p_i \le n$)。
输出格式
输出操作几次能使 $p$ 成为升序排列。
输入输出样例
输入 #1
3 2 1 2 3
输出 #1
0
输入 #2
3 1 3 1 2
输出 #2
1
输入 #3
4 2 1 3 2 4
输出 #3
1
输入 #4
4 2 2 3 1 4
输出 #4
2
第一个样例，因为已经是升序全排列了，所以不需要操作了
第二个样例，一次只能选择一个元素移动，选择3移动到尾部，操作一次即可
第三个样例，在第一次操作中选择元素 $2$ 和 $1$，在第二次操作中选择元素 $3$ 和 $4$ 那么该排列将按如下方式排序：$[\color{red}{2}, \color{black}3, \color{red}{1}, \color{black}4] \rightarrow [\color{blue}{3}, \color{blue}{4}, \color{red}{1}, \color{red}{2}\color{black}] \rightarrow [1,2, \color{blue}{3}, \color{blue}{4}\color{black}]$ 。
第二个样例，一次只能选择一个元素移动，选择3移动到尾部，操作一次即可
第三个样例，在第一次操作中选择元素 $2$ 和 $1$，在第二次操作中选择元素 $3$ 和 $4$ 那么该排列将按如下方式排序：$[\color{red}{2}, \color{black}3, \color{red}{1}, \color{black}4] \rightarrow [\color{blue}{3}, \color{blue}{4}, \color{red}{1}, \color{red}{2}\color{black}] \rightarrow [1,2, \color{blue}{3}, \color{blue}{4}\color{black}]$ 。
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？