[ABC276C] Previous Permutation

ID: 19004

传统题

2000ms

1024MiB

难度: 2

上传者:

配点 : $300$ 点

問題文

$(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)$ に対し、 $A$ が $B$ より辞書順で真に小さいとは、ある整数 $1 \leq i \leq N$ が存在して、下記の $2$ つがともに成り立つことをいいます。

入力は以下の形式で標準入力から与えられる。

$N$

$P_1$ $\ldots$ $P_N$

求める順列を $Q = (Q_1, \dots, Q_N)$ として、 $Q_1, \dots, Q_N$ をこの順に空白区切りで一行に出力せよ。

3
3 1 2

2 3 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)$ です。

10
9 8 6 5 10 3 1 2 4 7

9 8 6 5 10 2 7 4 3 1