题解 | #两个序列#

将数组a中的数字变成和数组b中的数字顺序一样（两个序列都是由相同的无重复数字集合组成的），可以通过将每个唯一的数字映射到唯一的下标上。目标数组b中，记$b[po{s}_1]=b_1,b[po{s}_2]=b_2,\mathrm{.}\mathrm{.}\mathrm{.},b[po{s}_j]=b_j,\mathrm{.}\mathrm{.}\mathrm{.},b[po{s}_n]=b_{n}b[pos\_1]=\; b\_1,b[pos\_2]=\; b\_2,...,b[pos\_j]=\; b\_j,...,b[pos\_n]=b\_n$，将数组a中对应的值（a[i]=b[j]）修改为$a[i]=po{s}_{j}a[i]=pos\_j$。

举例：a=[6,8,7,9,10] b=[9,10,8,6,7]，则重新映射之后，a[4,3,5,1,2]，b=[1,2,3,4,5]，目标是首位移动最少多少次a可以变成b。

思路：最长递增子串（不是子序列）。最长的递增子串看作是不动的，将其区间前后的数字进行移动，可以移动到任何地方，但一定要移动才能到最后的目标（整个都是递增的）。找到的递增子串越长，移动的次数越少。

#include <iostream>
#include <algorithm>
#include <map>
using namespace std;
const int N = 100010;
int a[N];
map<int,int> mp;
int ans;
int cnt;
int main()
{
    int n;
    int b;
    scanf("%d",&n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d",&a[i]);
    }
    for(int i = 01;i<=n;i++)
    {
        scanf("%d",&b);
        mp[b] = i;  //记录b中 数字和对应的下标
    }
    //将 数组a也映射到1-n范围内的数字  ，a[i]放的是b数组中 这个数字a_i的下标位置，
    for(int i = 1;i<=n;i++) 
    {
        a[i] = mp[a[i]];
    }
    //这之后，就是判断a中保存的位置顺序和 b的位置顺序需要交换的次数
    //找最长上升子串
    for(int i = 2;i<=n;i++)
    {
        if(a[i]>a[i-1])  //不断更新最长上升子串的长度
            ans = max(ans, ++cnt);
        else
            cnt = 1;
    }
    printf("%d\n",n-ans);
    return 0;
}