Erase and Rotate

题目描述

给定一个序列 $P = (p_1,p_2,\ldots,p_N)$，其中恰好包含 $1,2,\ldots,N$ 各一次。
你可以最多进行总计介于 $0$ 到 $K$ 次之间的以下操作（顺序任意）：

选择 $P$ 的一个项并将其移除。 将 $P$ 的最后一项移动到开头。

求通过这些操作可以得到的按字典序最小的 $P$。

输入格式

输入按下列格式从标准输入给出： $N$ $K$ $p_1$ $p_2$ $\ldots$ $p_N$

输出格式

输出通过操作可以得到的按字典序最小的 $P$，各数之间以空格分隔。

5 3
4 5 2 3 1

1 2 3

3 0
3 2 1

3 2 1

15 10
12 10 7 2 8 11 9 1 6 14 3 15 13 5 4

1 3 4 7 2 8 11 9

提示

$1 \leq N \leq 2 \times 10^5$ $0 \leq K \leq N-1$ $1 \leq p_i \leq N$ $(p_1,p_2,\ldots,p_N)$ 恰好包含 $1,2,\ldots,N$ 各一次。 输入中的所有数值均为整数。下面的操作能使 $P$ 变为 $(1,2,3)$。

移除第一项使 $P$ 变为 $(5,2,3,1)$。 将最后一项移到开头使 $P$ 变为 $(1,5,2,3)$。 移除第二项使 $P$ 变为 $(1,2,3)$。

没有办法得到比 $(1,2,3)$ 字典序更小的 $P$，所以这是答案。
你也可能无法执行操作。

标签: AtCoder|abc262F

来源

AtCoder|abc262F