「题解」P8184 [USACO22FEB] Photoshoot 2 B

· · 题解

这一题本质上是一种 类逆序对，

我们可以建立一个数组 pos 表示一个值在 目标序列 b 中的位置，即：

pos_{b_i}=i\ (1\le i\le n)

那么，

由于序列 a 中的每一个数字 都会在序列 b 中出现，

所以我们就能令 a_i=pos_{a_i}。

于是，就可用类似于 逆序对 的方法求解。

Code:

#include<bits/stdc++.h>
using namespace std;
int n,a[100005],b[100005],pos[100005],maxn=0,ans=0;
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",a+i);
    for(int i=1;i<=n;i++)
        scanf("%d",b+i),pos[b[i]]=i;
    for(int i=1;i<=n;i++)
        a[i]=pos[a[i]];
    for(int i=1;i<=n;i++)
    {
        if(a[i]>maxn)
            maxn=a[i];
        else
            ++ans;
    }
    printf("%d",ans);
    return 0;
}