AT_abc276_c [ABC276C] Previous Permutation

题目描述

给定一个 $(1,\ \dots,\ N)$ 的排列 $P = (P_1,\ \dots,\ P_N)$。但保证 $(P_1,\ \dots,\ P_N) \neq (1,\ \dots,\ N)$。

将 $(1,\ \dots,\ N)$ 的所有排列按字典序从小到大排列，假设 $P$ 是第 $K$ 个。请你求出字典序第 $K-1$ 个排列。

什么是排列？
$(1,\ \dots,\ N)$ 的排列是指将 $(1,\ \dots,\ N)$ 重新排列得到的数列。

什么是字典序？
对于长度为 $N$ 的数列 $A = (A_1,\ \dots,\ A_N),\ B = (B_1,\ \dots,\ B_N)$，若存在某个整数 $1 \leq i \leq N$，同时满足以下两个条件，则称 $A$ 字典序严格小于 $B$：

• $(A_{1},\ldots,A_{i-1}) = (B_1,\ldots,B_{i-1})$
• $A_i < B_i$

输入格式

输入从标准输入中给出，格式如下：

$N$ $P_1$ $\ldots$ $P_N$

输出格式

请输出所求的排列 $Q = (Q_1,\ \dots,\ Q_N)$，用空格分隔，输出一行。

输入输出样例 #1

输入 #1

3
3 1 2

输出 #1

2 3 1

输入输出样例 #2

输入 #2

10
9 8 6 5 10 3 1 2 4 7

输出 #2

9 8 6 5 10 2 7 4 3 1

说明/提示

限制条件

• $2 \leq N \leq 100$
• $1 \leq P_i \leq N \quad (1 \leq i \leq N)$
• $P_i \neq P_j \quad (i \neq j)$
• $(P_1,\ \dots,\ P_N) \neq (1,\ \dots,\ N)$
• 输入的所有值均为整数

样例解释 1

将 $(1,\ 2,\ 3)$ 的所有排列按字典序从小到大排列如下：

• $(1,\ 2,\ 3)$
• $(1,\ 3,\ 2)$
• $(2,\ 1,\ 3)$
• $(2,\ 3,\ 1)$
• $(3,\ 1,\ 2)$
• $(3,\ 2,\ 1)$

因此 $P = (3,\ 1,\ 2)$ 是第 $5$ 个，所求的排列，即第 $5-1=4$ 个排列为 $(2,\ 3,\ 1)$。

由 ChatGPT 4.1 翻译