102625: [AtCoder]ABC262 F - Erase and Rotate
Description
Score : $500$ points
Problem Statement
You are given a sequence $P = (p_1,p_2,\ldots,p_N)$ that contains $1,2,\ldots,N$ exactly once each.
You may perform the following operations between $0$ and $K$ times in total in any order:
- Choose one term of $P$ and remove it.
- Move the last term of $P$ to the head.
Find the lexicographically smallest $P$ that can be obtained as a result of the operations.
Constraints
- $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)$ contains $1,2,\ldots,N$ exactly once each.
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
$N$ $K$ $p_1$ $p_2$ $\ldots$ $p_N$
Output
Print the lexicographically smallest $P$ that can be obtained as a result of the operations, separated by spaces.
Sample Input 1
5 3 4 5 2 3 1
Sample Output 1
1 2 3
The following operations make $P$ equal $(1,2,3)$.
- Removing the first term makes $P$ equal $(5,2,3,1)$.
- Moving the last term to the head makes $P$ equal $(1,5,2,3)$.
- Removing the second term makes $P$ equal $(1,2,3)$.
There is no way to obtain $P$ lexicographically smaller than $(1,2,3)$, so this is the answer.
Sample Input 2
3 0 3 2 1
Sample Output 2
3 2 1
You may be unable to perform operations.
Sample Input 3
15 10 12 10 7 2 8 11 9 1 6 14 3 15 13 5 4
Sample Output 3
1 3 4 7 2 8 11 9
Input
题意翻译
给定一个排列 $\{a_n\}$，有两种操作： - 将最后数提到最前（Rotate） - 删除一个数（Erase） 求操作不超过 $k$ 次后最小字典序。 第一行输入 $n,k$，第二行输入 $\{a_n\}$。输出一行数，代表最小字典序。Output
问题描述
给你一个序列 $P = (p_1,p_2,\ldots,p_N)$，其中恰好包含$1,2,\ldots,N$各一次。
你可以按任意顺序进行0到$K$次以下操作：
- 选择$P$中的一个项并删除它。
- 将$P$的最后一个项移动到头部。
找出通过操作可以得到的字典序最小的$P$。
约束条件
- $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$各一次。
- 输入中的所有值都是整数。
输入
从标准输入获取以下格式的输入：
$N$ $K$ $p_1$ $p_2$ $\ldots$ $p_N$
输出
用空格分隔，打印通过操作可以得到的字典序最小的$P$。
样例输入1
5 3 4 5 2 3 1
样例输出1
1 2 3
以下操作使$P$等于$(1,2,3)$。
- 删除第一个项使$P$等于$(5,2,3,1)$。
- 将最后一个项移动到头部使$P$等于$(1,5,2,3)$。
- 删除第二个项使$P$等于$(1,2,3)$。
无法使$P$字典序小于$(1,2,3)$，所以这是答案。
样例输入2
3 0 3 2 1
样例输出2
3 2 1
你可能无法进行操作。
样例输入3
15 10 12 10 7 2 8 11 9 1 6 14 3 15 13 5 4
样例输出3
1 3 4 7 2 8 11 9