No.1115 二つの数列 / Two Sequences
タグ : / 解いたユーザー数 238
作問者 :
null
/ テスター :
tyawanmusi
問題文
null くんは長さ $n$ の順列 $P = \{1, 2, \dots, n\}$ を並べ替えた数列 $A = \{a_1, a_2, \dots, a_n\}, B= \{b_1, b_2, \dots, b_n\}$ を持っています。
null くんは以下の操作を繰り返して $A = B$ としたいです。
- $1 \le i \le n - 1$ を満たす整数 $i$ を一つ選び、$a_i$ と $a_{i+1}$ を入れ替える。
ただし、$1 \le j \le n$ を満たすすべての $j$ について $a_j = b_j$ が成り立つとき、$A=B$ とします。
入力
$n$ $a_1 \ a_2 \ \dots a_n$ $b_1 \ b_2 \ \dots b_n$
$1 \le n \le 10^5$
$A, B$ は順列 $P$ を並べ替えた数列である。
入力はすべて整数である。
出力
$A = B$ とするのに必要な操作回数の最小値を一行に出力してください。 最後に改行してください。
サンプル
サンプル1
入力
5 1 5 4 2 3 2 1 4 3 5
出力
5
例えば、
$1, 5, 4, 2, 3 \rightarrow 1, 5, 2, 4, 3 \rightarrow 1, 2, 5, 4, 3 \rightarrow 2, 1, 5, 4, 3 \rightarrow 2, 1, 4, 5, 3 \rightarrow 2, 1, 4, 3 ,5$
と操作をすると操作回数は最小になり、これ未満の操作回数で条件を達する方法はありません。
サンプル2
入力
7 5 6 7 1 3 4 2 5 6 7 1 3 4 2
出力
0
最初から $A = B$ の場合もあります。
サンプル3
入力
15 5 2 8 13 4 11 12 14 6 9 7 1 3 10 15 9 12 15 5 3 2 14 13 1 6 8 11 10 4 7
出力
52
サンプル4
入力
5 4 1 5 3 2 5 2 1 4 3
出力
6
サンプル5
入力
26 21 13 12 24 4 7 20 1 10 8 22 14 3 16 9 11 15 5 19 18 23 2 17 6 25 26 17 3 18 7 8 14 5 15 1 12 11 13 2 4 22 9 21 19 24 16 20 6 25 26 10 23
出力
150
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。