眼红的 Medusa

题意

给出两个获奖名单：

第一个名单：获得科技创新奖的人；
第二个名单：获得特殊贡献奖的人。

要求输出同时出现在两个名单中的编号，并且输出顺序要保持第一个名单中的顺序。

思路

先看一个可以直接验证想法的朴素解：

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#include <bits/stdc++.h>
using namespace std;

int a[1005], b[1005];

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

    int n, m;
    cin >> n >> m;

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

    bool first = true;
    for (int i = 1; i <= n; i++) {
        bool ok = false;
        for (int j = 1; j <= m; j++) {
            if (a[i] == b[j]) {
                ok = true;
                break;
            }
        }
        if (ok) {
            if (!first) cout << ' ';
            cout << a[i];
            first = false;
        }
    }
    cout << '\n';

    return 0;
}

朴素做法是：枚举第一个名单中的每个人，再到第二个名单里线性查找。这个做法是 $O(nm)$ ，当 n,m 都达到 100000 时会超时。

本题真正需要反复回答的问题是：某个编号是否出现在第二个名单中。可以先把第二个名单排序，然后对第一个名单中的每个编号做二分查找。

rbook《二分查找》文章中的基础模型是：在有序序列中找到第一个 >= x 的位置。本题也是这样：

text

1pos = lower_bound(b, x)

如果 pos 没有越界，并且 b[pos] == x，说明 x 在第二个名单中出现过，就输出 x。

样例查找过程

样例中第二个名单排序后是：

text

12 8 9

这张表展示第一个名单中每个编号的判断过程。

第一个名单编号	二分查找结果	是否输出
`2`	找到 `2`	是
`15`	找不到	否
`6`	找不到	否
`8`	找到 `8`	是

所以最终输出 2 8。注意输出顺序来自第一个名单，不是排序后的顺序。

代码

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#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100000 + 5;
int a[MAXN], b[MAXN];

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

    int n, m;
    cin >> n >> m;

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

    sort(b + 1, b + m + 1);

    bool first = true;
    for (int i = 1; i <= n; i++) {
        // 在第二个获奖名单中查找 a[i]，输出顺序仍然按第一个名单来。
        int pos = lower_bound(b + 1, b + m + 1, a[i]) - b;
        if (pos <= m && b[pos] == a[i]) {
            if (!first) cout << ' ';
            cout << a[i];
            first = false;
        }
    }
    cout << '\n';

    return 0;
}

复杂度

排序第二个名单需要 $O(m log m)$ 。
对第一个名单的每个编号做一次二分，需要 $O(n log m)$ 。
总时间复杂度 $O(m log m + n log m)$ 。
空间复杂度 $O(n + m)$ 。

总结

这题是“排序后查找集合成员”的入门题。

如果题目要求保持第一个名单的输出顺序，就不能把两个名单都排序后直接输出；正确做法是只排序用于查询的第二个名单，再按第一个名单原顺序逐个判断。

目录

题意

思路

样例查找过程

代码

复杂度

总结