题解：P8184 [USACO22FEB] Photoshoot 2 B

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

我们可以建立一个数组

pos

表示一个值在目标序列

b

中的位置，即：

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

那么，由于序列

a

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

所以我们就能令

a _ {i} = pos _ {a _ {i}}

。

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

Code:

CPP

#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;
}

题解：P8184 [USACO22FEB] Photoshoot 2 B

文章操作

Code:

相关推荐

评论

题解：P8184 [USACO22FEB] Photoshoot 2 B