#D. 希蒙整队

    传统题 1000ms 256MiB

希蒙整队

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

希蒙要给班上 NN 个编号互不相同的同学整队 1N105(1\leq N\leq 10^5)(按 1N1\cdots N 编号)。

他们起初按照 a1,a2,,aNa_1,a_2,\cdots,a_N 的顺序排列。现在需要按照 b1,,bNb_1,\cdots,b_N 顺序重排列。每次操作,可以任选其中一个同学,将其向左边移动任意距离。

请计算按所需顺序排列所需的最少操作次数。

输入格式

输入的第一行包含 NN,第二行包含 a1,a2,,aNa_1,a_2,\cdots,a_N,第三行包含 b1,b2,,bNb_1,b_2,\cdots,b_N

输出格式

输出所需的最少修改次数。

样例 #1

样例输入 #1

5
1 2 3 4 5
1 2 3 4 5

样例输出 #1

0

样例 #2

样例输入 #2

5
5 1 3 2 4
4 5 2 1 3

样例输出 #2

2

数据范围

测试用例 363\sim 6 满足 N100N\leq 100

测试用例 7107\sim 10 满足 N5000N\leq 5000

测试用例 111411\sim 14 不满足额外的约束。

样例解释1

在此示例中,数字已按所需顺序排列,因此无需修改。

样例解释2

在这个例子中,两个修改就足够了。 这是一种方法:

1.1.选择数字 44 并将其向左移动四个位置。

2.2.选择数字 22 并将其向左移动两个位置。

   5 1 3 2 4
-> 4 5 1 3 2
-> 4 5 2 1 3

秋季训练赛2

未参加
状态
已结束
规则
IOI
题目
6
开始于
2023-9-21 18:30
结束于
2023-9-21 21:30
持续时间
3 小时
主持人
参赛人数
72