看到互不相同的元素，一定想到hash！

题目简述

n个互不相同的数，排列组合成两个序列a和b，每次操作只能从a中选择第一个或最后一个数字并插入a中任意位置，问最少需要多少次操作把a变成b。

算法分析

设n个元素为x1, x2, ..., xn，因为要从a变成b，所以把b中的值[xk1, xk2, ..., xkn]用hash_map映射为[0, 1, ..., n-1]。

那么题目就变为，把a中的映射值[i1, i2, ..., in] 变为固定值 [0, 1, ..., n-1]。

这样此题就变为求a数组中的最长上升子串问题了

C++代码

详细分析：

若 ai, ai+1, ..., aj是最长上升子串，则一定有 ai-1 > ai，aj+1 < aj， 那么前面从a0到ai-1的i个值都需要依次移动，后面从aj到an-1的n-j个值都需要依次移动。

因为我们只能每次移动首元素或者尾元素，哪怕a0到ai-2都不需要移动，我们为了移动ai-1，也只能把它们全都移动到ai-1后面，使ai-1变为首元素，从而移动ai-1到正确位置；

同理，为了移动aj+1，aj+2到an的元素无论如何都需要被移动。例如：[1,2,4,3,5,6,8,7,9,10]的最长上升子串为"3,5,6,8"

所以总的移动次数就是 n - maxlen。

#include<iostream>
#include<vector>
#include<algorithm>
#include <unordered_map>
using namespace std;

int No10_hash(vector<int>& a, vector<int>& b) {
    int n = a.size();
    // 1. 因为要把a编程b，所以对b做映射，b中的值[A,B,C,D] 映射为 [0,1,2,3]
    unordered_map<int, int> mp;
    for (int i = 0; i < n; i++) mp[b[i]] = i;
    // 2. 这样把a也变成映射值后，就是让a变成[0,1,2,3]这个固定值，那就是求a的最长上升子串
    int len = 0, cur = 0, curi = -1;
    for (int i = 0; i < n; i++) {
        if (mp[a[i]] > curi) cur++;
        else {
            len = max(len, cur);
            cur = 1;
        }
        curi = mp[a[i]];
    }
    len = max(len, cur);
    //若 ai, ai+1, ..., aj是最长上升子串
    //则一定有 ai-1 > ai，aj+1 < aj，
    //那么从a0到ai-1的i个值都需要依次移动，从aj到an-1的n-j个值都需要依次移动
    return n - len; //所以答案为 n-len
}

int main() {
    int n;
    cin>>n;
    vector<int> a(n, 0);
    vector<int> b(n, 0);
    for(int i=0; i<n; i++) cin>>a[i];
    for(int i=0; i<n; i++) cin>>b[i];
    
    cout<<No10_hash(a, b)<<'\n';
    return 0;
}