[USACO22FEB] Photoshoot 2 B 题解

考虑 $O(N)$ 算法。 样例的数据比较简单，我们来换一个： | | 0 |1 |2 |3 |4 | | -----------: | -----------: | -----------: | -----------: | -----------: | -----------: | | $a$ | 5 | 1 | 4 | 3 | 2 | | $b$ | 4 | 5 | 2 | 1 | 3 | 实际上的对应关系是这样的：  1. $b[0]\neq a[0]$，于是将 $\text{(原来的)}a[2]$ 移动至下标 $0$。但是我们**不改变数组**（整个过程中都如此），仅仅知道需要这样做。 2. $b[1]= a[0]$。为什么对应的是 $a[0]$ 呢？因为之前已经将 $\text{(原来的)}a[2]$ 移动过去了，但是数组没改变，所以 $\text{(新的)}a[1]$ 实际上是 $\text{(原来的)}a[0]$。 3. $b[2]\neq a[1]$。所以将 $\text{(原来的)}a[4]$ 移动至下标 $1$。但是我们依然不改变数组。 4. $b[3]= a[1]$。在实际上，$a[1]$ 是 $\text{(新的)}a[3]$，因为前面插入了两个数。 5. $b[4]= a[3]$。同理，$\text{(原来的)}a[3]$ 实际上是 $\text{(新的)}a[4]$。因为它的前面其实只多了一个 $\text{(原来的)}a[4]=2$，所以只是往后移了一位。 过程就是这样，似乎有点复杂。 实现的过程中，我们遍历 $b$，用一个 $fix$ 值来修正对应 $a$ 的下标。也就是说 $b[i]$ 对应 $a[i-fix]$。 当我们遇到这两个数不一样的情况，就要将 $a[i-fix]$ 后面的某个数（记为 $a[x]$）移动到当前数的前面，且 $\text{新}fix = \text{老}fix +1$。（这样到了 $b[i+1]$ 的时候，由于 $i+1-(\text{老}fix+1)=i-\text{老}fix$，所以还是对应 $a[i-\text{老}fix]$ **目前的**这个数）。 如果后面遇到了 $a[x]$，因为它实际上已经移动到前面去了，所以对应的数应该是 $a[x]$ 后面的数，所以 $\text{新}fix = \text{老}fix -1$ (由于$i-(\text{老}fix-1)=i+1-\text{老}fix$)，于是就对应了 $a[x+1]$。 怎么知道后面遇到了这个 $a[x]$ 呢？用数组打标记（即代码中 `flag[]`）即可。 由于本人说理能力太逊，建议~~必须~~配合代码食用。 ```cpp #include <bits/stdc++.h> using namespace std; int n; int a[100005], b[100005]; int flag[100005]; int main() { cin >> n; for (int i = 0; i < n; i++) { cin >> a[i]; } int fix = 0; int ans = 0; for (int i = 0; i < n; i++) { cin >> b[i]; while (flag[a[i-fix]] == 1) fix--; // 遇到 a[x]。注意是 while，因为可能遇到一连串都是往前移动过的。 if (b[i] != a[i-fix]) { fix++; ans++; flag[b[i]] = 1; } } cout << ans << endl; return 0; } ``` 附 [USACO 官方题解](http://www.usaco.org/current/data/sol_prob2_bronze_feb22.html)，虽然我看不懂。