个人网站名字大全,成都十大建筑设计公司,wordpress创建数据库类型选什么,seo快速入门教程Photoshoot 2
题目描述
在一个似曾相识的场景中#xff0c;Farmer John 正在将他的 N 头奶牛#xff08;1≤N≤10^5#xff09;排成一排#xff08;为了方便将它们按 1⋯1⋯N 编号#xff09;#xff0c;以便拍照。
最初#xff0c;奶牛从左到右按照 a1,a2,⋯,aN 的顺…Photoshoot 2
题目描述
在一个似曾相识的场景中Farmer John 正在将他的 N 头奶牛1≤N≤10^5排成一排为了方便将它们按 1⋯1⋯N 编号以便拍照。
最初奶牛从左到右按照 a1,a2,⋯,aN 的顺序排列。Farmer John 的目标是按照 b1,⋯,bN 从左到右的顺序排列奶牛。为此他可以对排列顺序进行一系列修改。每次修改为选择一头奶牛并将其向左移动一些位置。
请计算农民约翰按所需顺序排列奶牛所需的最少修改次数。
输入格式
输入的第一行包含 N第二行包含 a1,a2,⋯,aN第三行包含 b1,b2,⋯,bN 。
输出格式
输出产生 Farmer John 所需顺序所需的最少修改次数。
数据范围
测试用例 3∼6满足N*≤100
测试用例 7∼10满足 N*≤5000
测试用例 11∼14不满足额外的约束。
样例解释1
在此示例中奶牛已按所需顺序排列因此无需修改。
样例解释2
在这个例子中两个修改就足够了。 这是 Farmer John 重新排列奶牛的一种方法 选择奶牛 4 并将其向左移动四个位置。 选择奶牛 2 并将其向左移动两个位置。
输入输出样例
输入 #1
5
1 2 3 4 5
1 2 3 4 5输出 #1
0输入 #2
5
5 1 3 2 4
4 5 2 1 3输出 #2
2题解
思想来源于https://blog.csdn.net/guolianggsta/article/details/134736006 import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner in new Scanner(System.in);int n in.nextInt();int[] a new int[n1];int[] b new int[n1];int ans 0;for(int i 1; i n; i) {a[i] in.nextInt(); //记录n个数}for(int i 1; i n; i) {int t in.nextInt();b[t] i; // 记录n个数在b数组中的下标}int pre b[a[1]];for(int i 2; i n; i) {if(pre b[a[i]]) { //相对位置无变化pre b[a[i]];}else {ans;}}System.out.println(ans);}
}
