[USACO22FEB] Photoshoot 2 B 题解

Zirnc · 2022-03-05 16:40:38 · 题解

考虑 O(N) 算法。

实际上的对应关系是这样的：

过程就是这样，似乎有点复杂。

实现的过程中，我们遍历 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[]）即可。

由于本人说理能力太逊，建议必须配合代码食用。

#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 官方题解，虽然我看不懂。