p8184题解

cfkk · 2022-03-05 20:11:00 · 题解

想要写出这道题就要想一个关键的问题：到底什么数应该移动？

自己想一下，想好了往下看。

正文开始：

相信大家刚拿到这道题，肯定会毫无头绪，但是我们设一个映射数组为 dep ，dep_i 表示 a_i 在 b_i 中的位置，让我们以样例2举例：

如果有这个数列，那么我们就会发现一个事实：一个数如果要往左移，那么左面一定有比它大的值。

所以问题就可以转换成左面有多少个大于 dep_i 的值。

代码来喽：

#include<bits/stdc++.h>
using namespace std;
inline int read()
{
    char ch=getchar();
    int s=0,w=1;
    while(ch<'0'||ch>'9')
    {
        if(ch=='-'){w=-1;}
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        s=(s<<1)+(s<<3)+ch-48;
        ch=getchar();
    }
    return w*s;
}
inline void print(int x)
{
    if(x<0){putchar('-');x=-x;}
    if(x>9){print(x/10);}
    putchar(x%10+'0');
}
int a[100001],b[100001],dep[100001],kep[100001];
signed main()
{
    int n=read();
    for(int i=1;i<=n;i++){a[i]=read();}
    for(int i=1;i<=n;i++){b[i]=read();dep[b[i]]=i;}
    for(int i=1;i<=n;i++){kep[i]=dep[a[i]];}//映射序列
    int cnt=0,x=0;
    for(int i=1;i<=n;i++)
    {
        x=x>kep[i]?x:kep[i];//求左面是否有比它大的值
        if(x>kep[i]){cnt++;}//如果有就答案加1 
    }
    print(cnt);
    return 0;
}