题目描述

给定一个整数数组 $A$，其包含 $n$ 个正整数 $a_1,\ a_2,\ \cdots,\ a_n$ 以及一个整数数组 $B$，其包含 $m$ 个正整数 $b_1,\ b_2,\ \cdots,\ b_m$。 请从数组 $A$ 中挑选一个元素 $a$ 并从数组 $B$ 中挑选一个元素 $b$，使得 $a+b$ 既不包含于 $A$ 也不包含于 $B$。
例如，如果 $A=[2,\ 1,\ 7]$ 而 $B=[1,\ 3,\ 4]$，则可以从 $A$ 中选取 $1$，从 $B$ 中选取 $4$，这样得到的数字 $1+4=5$ 既不在 $A$ 中，也不在 $B$ 中。
但是，我们不能从 $A$ 中选取 $2$，从 $B$ 中选取 $1$，因为得到的数字 $2+1=3$ 包含于 $B$。
可以证明这样的数对一定存在，如果答案不唯一则输出任意合理答案均可。

输入

第一行包含整数 $n$。 第二行包含 $n$ 个整数 $a_1,\ a_2,\ \cdots,\ a_n$。
第三行包含整数 $m$。
第四行包含 $m$ 个整数 $b_1,\ b_2,\ \cdots,\ b_m$。

输出

共一行，输出 $a$ 和 $b$，中间用空格隔开。

样例

样例输入

1
20
2
10 20

样例输出

20 20

数据规模

对于 $30\%$ 的数据，$1≤n,\ m≤10$
对于 $100\%$ 的数据，$1≤n,\ m≤100,\ 1≤a_i,\ b_i≤200$

算法1

暴力枚举

我们可以看到，本题的数据量极小。也就是说，使用 $O(n^2)$ 的算法，我们也就是计算 $100*100=10^4$，完全可以保证在 $1$ 秒内完成。

时间复杂度

$O(nm)$

空间复杂度

$O(n)$

C++ 代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN=4e2+10;
int a[MAXN];
int b[MAXN];
bool f[MAXN];
int main() {
    //freopen("1.in", "r", stdin);
    //freopen("1.out", "w", stdout);
    int n;
    scanf("%d", &n);
    for (int i=1; i<=n; i++) {
        scanf("%d", &a[i]);
        f[a[i]]=true;
    }
    int m;
    scanf("%d", &m);
    for (int i=1; i<=m; i++) {
        scanf("%d", &b[i]);
        f[b[i]]=true;
    }

    for (int i=1; i<=n; i++) {
        for (int j=1; j<=m; j++) {
            int t=a[i]+b[j];
            if (false==f[t]) {
                printf("%d %d\n", a[i], b[j]);
                return 0;
            }
        }
    }

    return 0;
}

算法2

优化

本题要求找出一个样例即可。本题要求为 $c=a_i+b_i$，而且要求 $c$ 不在队列 $a$ 和 $b$ 中。
因此我们可以非常容易知道，序列 $a$ 的最大值加上序列 $b$ 的最大值，自然不在这两个序列中。
这个非常容易使用反证法证明。

时间复杂度

O(n)

空间复杂度

O(1)

C++ 代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN=4e2+10;
int main() {
    //freopen("1.in", "r", stdin);
    //freopen("1.out", "w", stdout);
    int n;
    scanf("%d", &n);
    int maxa=0;
    for (int i=1; i<=n; i++) {
        int x;
        scanf("%d", &x);
        maxa=max(maxa, x);
    }
    int m;
    scanf("%d", &m);
    int maxb=0;
    for (int i=1; i<=m; i++) {
        int x;
        scanf("%d", &x);
        maxb=max(maxb, x);
    }

    printf("%d %d\n", maxa, maxb);

    return 0;
}