No.1115 Two Sequences
タグ : / 解いたユーザー数 247
作問者 :
null
/ テスター :
tyawanmusi
Problem Statement
null has sequences $A = \{a_1, a_2, \dots, a_n\}, B= \{b_1, b_2, \dots, b_n\}$, each obtained by rearranging the permutation $P = \{1, 2, \dots, n\}$ of length $n$.
null wants to make $A = B$ by repeating the following operation.
- Choose an integer $i$ satisfying $1 \le i \le n - 1$, and swap $a_i$ and $a_{i+1}$.
Here, $A=B$ holds when $a_j = b_j$ for all $j$ satisfying $1 \le j \le n$.
Input
$n$ $a_1 \ a_2 \ \dots a_n$ $b_1 \ b_2 \ \dots b_n$
$1 \le n \le 10^5$
$A, B$ are sequences obtained by rearranging the permutation $P$.
All inputs are integers.
Output
Output the minimum number of operations required to make $A = B$ on one line. Print a newline at the end.
Sample
Sample 1
Input
5 1 5 4 2 3 2 1 4 3 5
Output
5
For example, performing the operations as
$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$
gives the minimum number of operations; there is no way to satisfy the condition with fewer operations.
Sample 2
Input
7 5 6 7 1 3 4 2 5 6 7 1 3 4 2
Output
0
It is possible that $A = B$ from the beginning.
Sample 3
Input
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
Output
52
Sample 4
Input
5 4 1 5 3 2 5 2 1 4 3
Output
6
Sample 5
Input
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
Output
150
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。