编程题
### 问题描述 总所周知,小秋特别喜欢下棋。每次下完一局棋之后,小秋都要手动把所有的棋子归位,他认为这是一件很繁琐的事情,因此,他想要最小化归位棋子的操作数量。 已知所有棋子可以看作是 $n$ 个互不相同的数,每个棋子都有特定放置的位置,没有两个棋子放置的位置是相同的。一盘棋局结束后,第 $i$ 个棋子所在的位置是 $p_i$。 小秋每次只能交换两个棋子,他想要知道,最少要操作几次,才能把所有棋子都归位。 ### 输入格式 第 $1$ 行输入一个整数 $n$,表示棋子的数量。 第 $2$ 行输入 $n$ 个不超过 $n$ 且互不相同的数,第 $i$ 个数表示第 $i$ 个棋子特定放置的位置。 第 $3$ 行输入 $n$ 个不超过 $n$ 且互不相同的数,第 $i$ 个数表示第 $i$ 个棋子当前的位置。 ### 输出格式 输出仅 $1$ 行,包含一个整数,表示最小操作次数。 ### 样例输入 ``` 5 1 2 3 4 5 2 5 1 4 3 ``` ### 样例输出 ``` 3 ``` ### 说明 第 $1$ 次可以交换棋子 $1$ 和 棋子 $2$,序列变为了 $1,5,2,4,3$。 第 $2$ 次可以交换棋子 $2$ 和 棋子 $3$,序列变为了 $1,5,3,4,2$。 第 $3$ 次可以交换棋子 $2$ 和 棋子 $5$,序列变为了 $1,2,3,4,5$。 所以棋子就全部归位了。 ### 评测数据规模 对于 $20$% 的评测数据,$1 \leq n \leq 10^3$。 对于 $40$% 的评测数据,$1\leq n\leq 10^4$。 对于 $100$% 的评测数据,$1 \leq n\leq 10^5$。
查看答案
赣ICP备20007335号-2