P6393: 拍照2

---

【题目描述】

这是一个似乎很熟悉的情况，Farmer John 正在将他的 N 头编号为 1…N 的奶牛（1≤N≤10⁵）排成一排，以便拍照。
最初，奶牛从左到右按a1,a2,…,aN 的顺序排列。Farmer John 的目标是将奶牛从左到右按b1,…,bN 的顺序排列。为此，他可以对排序进行一系列修改操作。每次修改操作可以选择一头奶牛并将其向左移动一些位置。
请计算 Farmer John 将奶牛排列成所要求的顺序所需的最小修改次数。
输入格式（从终端 / 标准输入读入）：
输入的第一行包含 N。第二行包含 a1,a2,…,aN。第三行包含 b1,b2,…,bN。
输出格式（输出至终端 / 标准输出）：
输出将奶牛排列成所要求的顺序所需的最小修改次数。
输入样例：
5
1 2 3 4 5
1 2 3 4 5
输出样例：
0
在这个例子中，奶牛已经排列成所要求的顺序，所以无需进行修改操作。
输入样例：
5
5 1 3 2 4
4 5 2 1 3
输出样例：
2
在这个例子中，两次修改操作足够了。以下是一种 Farmer John 重新排列他的奶牛们的方式：
选择奶牛 44 并将其向左移动四个位置。
选择奶牛 22 并将其向左移动两个位置。
   5 1 3 2 4
-> 4 5 1 3 2
-> 4 5 2 1 3
测试点性质：
测试点 3-6 满足 N≤100。
测试点 7-10 满足N≤5000。
测试点 11-14 没有额外限制。
供题：Benjamin Qi
 

【输入】

输入的第一行包含 N。第二行包含 a1,a2,…,aN。第三行包含 b1,b2,…,bN。

【输出】

输出将奶牛排列成所要求的顺序所需的最小修改次数。

【提示】

测试点性质：

测试点 3-6 满足 N≤100。

测试点 7-10 满足N≤5000。

测试点 11-14 没有额外限制。

题目类型~

USACO2022-铜牌-2 

咻咻~

提交答案 状态 返回