Photoshoot 2

题目描述

看起来又是一个熟悉的场景，农夫约翰正在把他的 $N$ 头奶牛（$1\le N\le 10^5$）排成一列拍照，奶牛被方便地编号为 $1\ldots N$。 起初，奶牛从左到右按顺序 $a_1,a_2,\ldots,a_N$ 排列。 农夫约翰的目标是让奶牛从左到右按顺序 $b_1,\ldots,b_N$ 排列。为此，他可以对当前顺序进行一系列修改。每次修改都是选择一头奶牛，并将它向左移动若干个位置。 请计算为了让农夫约翰把奶牛排成目标顺序，所需的最少修改次数。

输入格式

第一行输入 $N$。 第二行输入 $a_1,a_2,\ldots,a_N$。 第三行输入 $b_1,b_2,\ldots,b_N$。

输出格式

输出产生农夫约翰目标排列所需的最少修改次数。

5
1 2 3 4 5
1 2 3 4 5

0

5
5 1 3 2 4
4 5 2 1 3

2

提示

在这个例子中，奶牛已经处于目标顺序，因此不需要任何修改。 在这个例子中，两次修改就足够了。下面是一种农夫约翰可以重新排列奶牛的方法： 选择奶牛 $4$，将它向左移动四个位置。 选择奶牛 $2$，将它向左移动两个位置。 5 1 3 2 4 -> 4 5 1 3 2 -> 4 5 2 1 3 评分： 测试点 3-6 满足 $N\le 100$。 测试点 7-10 满足 $N\le 5000$。 测试点 11-14 没有额外限制。 题目来源：Benjamin Qi

标签: USACO|2022|Bronze

来源

USACO|2022|Bronze