自动搬运

查看原文

来自洛谷，原作者为

	cfkk 一入OI深似海，从此AC是路人

搬运于2025-08-24 22:36:42，当前版本为作者最后更新于2022-03-05 20:11:00，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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

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

正文开始：

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

$a=[5,1,3,2,4]$

$b=[4,5,2,1,3]$

$dep=[2,4,5,3,1]$

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

所以问题就可以转换成左面有多少个大于 $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;
}