AT_arc114_f.[ARC114F] Permutation Division

NOI/NOI+/CTSC

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

给定一个 $1, 2, \cdots, N$ 的排列 $P$ 。

你可以将 $P$ 恰好分割成 $K$ 个非空的连续子序列，方式任意。

maroon 君会将你分割出的连续子序列重新排列并连接起来，得到一个新的排列 $Q$ 。maroon 君会选择使 $Q$ 字典序最大的排列方式。

你希望 $Q$ 的字典序尽可能小。请输出你在最优分割下得到的 $Q$ 。

输入格式

输入以如下格式从标准输入读入：

$N$ $K$ $P_1$ $P_2$ $\cdots$ $P_N$

输出格式

请输出你最优分割下得到的 $Q$ 。

输入输出样例

输入#1
```
3 2
1 2 3
```
输出#1
```
2 3 1
```
输入#2
```
4 3
4 3 1 2
```
输出#2
```
4 3 1 2
```

输入#3

20 7
10 5 8 2 1 9 12 20 15 3 7 6 19 4 11 17 13 14 16 18

输出#3

10 5 8 2 7 6 19 4 11 17 13 14 16 18 3 1 9 12 20 15

说明/提示

限制条件

$1 \leq N \leq 2 \times 10^5$
$1 \leq K \leq N$
$1 \leq P_i \leq N$
$P_i \neq P_j\ (i \neq j)$
输入均为整数

样例解释 1

对于 $P$ 的分割方式，可以是 $(1, 2), (3)$ 或 $(1), (2, 3)$ 。
前者情况下，maroon 君会将 $(3), (1, 2)$ 重新排列，得到 $Q = (3, 1, 2)$ 。
后者情况下，maroon 君会将 $(2, 3), (1)$ 重新排列，得到 $Q = (2, 3, 1)$ 。
因此，你应该选择后者的分割方式。

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页