小强有两个序列和,这两个序列都是由相同的无重复数字集合组成的,现在小强想把序列变成序列,他只能进行以下的操作:
从序列中选择第一个或者最后一个数字并把它插入中的任意位置。
问小强至少需要几次操作可以将序列变为序列。
一行一个整数表示序列的长度。
接下来两行每行个整数。
第一行表示序列,第二行表示序列。
保证给出的序列符合题意。
输出一行一个整数表示答案。
4 4 2 3 1 1 2 3 4
2
import java.util.*; public class Main { /* 更改题目 a=[D,B,C,A]; b=[A,B,C,D] 对 b 做映射 A->0; B->1; C->2; D->3 那么对应的 a 可根据映射规则更改为 a'=[3,1,2,0] 之后对 a' 做最长连续上升子数组即可 */ public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int[] a = new int[n]; int[] b = new int[n]; for (int i = 0; i < n; i ++) { a[i] = sc.nextInt(); } for (int i = 0; i < n; i ++) { b[i] = sc.nextInt(); } // 对 A 里面的数进行重新映射 Map<Integer, Integer> map = new HashMap<>(); for (int i = 0; i < n; i ++) { map.put(b[i], i); } // 利用映射规则对 B 进行更新映射 for (int i = 0; i < n; i ++) { a[i] = map.get(a[i]); } // 对更改之后的 b 做最长连续上升子序列 int res = 0; int cur = 1; for (int i = 1; i < n; i ++) { if (a[i]>a[i-1]) { cur += 1; res = Math.max(res, cur); } else { cur = 1; } } System.out.println(n - res); } }