Photoshoot 2

题意

给定初始排列 a 和目标排列 b。

一次操作可以选择一头牛，把它向左移动任意若干个位置。

求把 a 变成 b 的最少操作次数。

思路

先看一个 $O(N^2)$ 的直接判断：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-11 17:41
 * update_at: 2026-07-11 17:42
 */
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1005;

int n;
int a[MAXN], b[MAXN];
int pos_in_b[MAXN];
int relabel[MAXN];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = 1; i <= n; i++) {
        cin >> b[i];
        pos_in_b[b[i]] = i;
    }

    for (int i = 1; i <= n; i++) {
        relabel[i] = pos_in_b[a[i]];
    }

    int ans = 0;
    for (int j = 1; j <= n; j++) {
        bool need_move = false;
        for (int i = 1; i < j; i++) {
            if (relabel[i] > relabel[j]) {
                need_move = true;
            }
        }
        if (need_move) {
            ans++;
        }
    }

    cout << ans << '\n';

    return 0;
}

先把目标排列 b 重标号成 1,2,...,N。也就是说，牛 b[i] 的新编号是 i。

这样目标就是把重标号后的 a 排成递增顺序。

考虑当前位置的牛 a[j]。如果它左边存在一头牛 a[i]，满足：

text

1i < j 且 a[i] > a[j]

那么这两头牛在目标顺序中是反的。由于操作只能把被选中的牛向左移动，所以必须选择当前这头牛 a[j] 至少一次，才能改变这对相对顺序。

因此，一头牛是否必须移动，只取决于它左边是否出现过比它更大的重标号。

用 max_so_far 维护左边最大值：

如果当前 order > max_so_far，它是新的前缀最大值，不需要移动；
否则左边存在更大的值，它必须移动，答案加一。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-11 17:41
 * update_at: 2026-07-11 17:42
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;

int n;
int a[MAXN], b[MAXN];
int pos_in_b[MAXN];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = 1; i <= n; i++) {
        cin >> b[i];
        pos_in_b[b[i]] = i;
    }

    int ans = 0;
    int max_so_far = 0;

    for (int i = 1; i <= n; i++) {
        int order = pos_in_b[a[i]];
        if (order > max_so_far) {
            max_so_far = order;
        } else {
            ans++;
        }
    }

    cout << ans << '\n';

    return 0;
}

复杂度

只扫描排列常数次。

时间复杂度为 $O(N)$ ，空间复杂度为 $O(N)$ 。

总结

本题的关键是把目标排列重标号为递增序列。

重标号后，必须移动的牛正是那些左边存在更大值的牛，也就是不是前缀最大值的元素。

目录

题意

思路

代码

复杂度

总结