Photoshoot 2(Java)

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

输入 #2

5
5 1 3 2 4
4 5 2 1 3

输出 #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[n+1];
		int[] b = new int[n+1];
		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);
	}
}