题解：P8184 [USACO22FEB] Photoshoot 2 B

· · 题解

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

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

pos _ {b _ {i}}=i (1≤i≤n)

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

所以我们就能令 a _ {i} = pos _ {a _ {i}}。

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

Code:

#include <bits/stdc++.h>
using namespace std;

int n, a[100005], b[100005], p[100005];

int main() {
    cin >> n;
    for (int i = 1; i <= n; i ++) cin >> a[i];
    for (int i = 1; i <= n; i ++) {
        cin >> b[i];
        p[b[i]] = i;
    }
    for (int i = 1; i <= n; i ++) a[i] = p[a[i]];
    int ans = 0, maxn = 0;
    for (int i = 1; i <= n; i ++) {
        if (maxn > a[i]) ans ++;
        maxn = max(maxn, a[i]);
    }
    cout << ans << endl;
    return 0;
}