小O的子序列最值

OPPO 笔试真题 · 2024 秋招 · 移动开发

判题请到牛客原题提交。

题目描述

小O有两个长度为 $n$ 的数组，现在她想从这两个数组中分别选出一个非空子序列，使得从第一个数组中选出的子序列的最大值不大于从第二个数组中选出的子序列的最小值。

小O想知道两个子序列的长度之和最大是多少。

如果数组 $a$ 可以通过删除数组 $b$ 中的若干（可能为零或全部）元素得到，则数组 $a$ 是数组 $b$ 的子序列。

输入格式

第一行输入一个整数 $n\ (1 \leq n \leq 10^5 )$ 代表数组的长度。

第二行输入 $n$ 个整数 $a_1,a_2,\dots,a_n\ (1 \leq a_i \leq 10^9 )$ 代表第一个数组。

第三行输入 $n$ 个整数 $b_1,b_2,\dots,b_n\ ( 1 \leq b_i \leq 10^9 )$ 代表第二个数组。

输出格式

在一行上输出一个整数，表示两个子序列的长度之和最大是多少。如果无法选出满足条件的子序列，则输出 $-1$ 。

示例

示例 1

输入：

4
1 2 3 4
3 4 5 6

输出：

7

说明：

第一个子序列[1, 2, 3, 4]，第二个子序列 [4, 5, 6]，长度之和为 7。

---

解题思路

第一步：理解问题本质

「子序列」看起来和顺序有关，但题目只用到了两个量：所选部分的最大值与最小值。
这两个量只取决于「选了哪些元素」，与它们的先后顺序无关。于是：

从数组里选一个非空子序列 ⟺ 从数组里选一个非空的下标集合。

设 a 里选出的部分最大值为 x、b 里选出的部分最小值为 y，题目条件就是 x <= y。

第二步：暴力解法（为什么不能用）

枚举 a 的每个非空下标集合（2^n - 1 种），再枚举 b 的每个非空下标集合，
逐一检查 max(A) <= min(B)。复杂度 O(4^n)，而 n 最大 10^5，
这个方向没有任何优化余地。

第三步：固定门槛，让两边解耦

解法卡住的原因是「两边的选择互相牵制」。换一个角度：不再分别枚举两边，
而是先定一个门槛 v。

• 如果 a 选出的部分最大值不超过 v，那么 a 中所有 <= v 的元素都可以选进来
  —— 多选几个小的，最大值依然不超过 v，没有副作用。
• 如果 b 选出的部分最小值不小于 v，那么 b 中所有 >= v 的元素都可以选进来
  —— 多选几个大的，最小值依然不小于 v。

于是固定 v 之后，最优选择就是「a 中全部 <= v 的元素」加上「b 中全部 >= v 的元素」，
长度直接是

cnt_a(<= v) + cnt_b(>= v)

两边的选择互不影响，纠缠消失了。唯一要注意的是两个子序列都必须非空，
所以两项计数都必须大于 0。

第四步：门槛枚举哪些值

设某组最优解中 b 的最小值为 y，它的值一定来自数组 b 的某个元素。
以 v = y 作为门槛，cnt_b(>= v) 至少能覆盖最优解里的整个 B，
cnt_a(<= v) 也至少能覆盖最优解里的整个 A（因为 max(A) <= min(B) = v）。
也就是说，在 b 的取值上枚举门槛，一定能把最优解取到，不会漏。

反过来，任何一个门槛算出来的候选值都对应一组合法选法（取 a 中所有 <= v、
b 中所有 >= v）。两头夹住，答案就是所有门槛里的最大值。

实现上把 a、b 排序，再用二分：

• cnt_a(<= v) = bisect_right(a, v)
• cnt_b(>= v) = n - bisect_left(b, v)

所有门槛都不合法时输出 -1。

---

完整代码实现

import sys
from bisect import bisect_left, bisect_right


def solve() -> None:
    """枚举阈值 v，统计 a 中 <= v 与 b 中 >= v 的元素个数"""
    data = sys.stdin.buffer.read().split()
    if not data:
        return

    n = int(data[0])
    a = sorted(map(int, data[1:1 + n]))
    b = list(map(int, data[1 + n:1 + 2 * n]))
    sb = sorted(b)

    best = -1
    # 阈值只需要枚举 b 中出现过的值：最优解里 b 的最小值本身就是 b 的某个元素
    for v in set(b):
        ca = bisect_right(a, v)          # a 中 <= v 的个数
        if ca == 0:                      # a 这边必须非空
            continue
        cb = n - bisect_left(sb, v)      # b 中 >= v 的个数
        if cb == 0:                      # b 这边必须非空
            continue
        if ca + cb > best:
            best = ca + cb

    sys.stdout.write(str(best) + "\n")


if __name__ == "__main__":
    solve()

---

示例推演

以题面样例 a = [1,2,3,4]、b = [3,4,5,6]、n = 4 为例，只看 b 的去重值：

门槛 v	cnt_a(<= v)	cnt_b(>= v)	长度之和
3	3（1,2,3）	4（3,4,5,6）	7
4	4（1,2,3,4）	3（4,5,6）	7
5	4	2（5,6）	6
6	4	1（6）	5

最大值为 7。取门槛 v = 4 时，a 取全部 [1,2,3,4]（最大值 4），
b 取 [4,5,6]（最小值 4），4 <= 4 成立，长度 4 + 3 = 7，与说明一致。

再看 a = [5]、b = [1, 10]：门槛 v = 1 时 cnt_a(<= 1) = 0，
a 这边选不出任何元素，这个门槛不合法；门槛 v = 10 时两边计数都是 1，
答案是 2（取 A = {5}、B = {10}）。这组数据说明的是「两边都必须非空」这条限制，
而不是随便取一个门槛就能得到答案。

---

复杂度分析

解法	时间复杂度	空间复杂度	说明
暴力枚举两个下标集合	O(4^n)	O(n)	n = 20 就已是万亿级
排序 + 枚举门槛 + 二分	O(n log n)	O(n)	推荐，n = 10^5 轻松通过

---

易错点总结

1. 把「子序列」当成「子数组」

子序列可以跳着取。正因为能跳，门槛方案才能「把 a 中所有 <= v 的元素都拿进来」，
不必是连续的一段。

2. 忘记两个子序列都必须非空

cnt_a(<= v) 或 cnt_b(>= v) 为 0 的门槛不合法，要跳过；
一个合法门槛都没有时输出 -1。样例之外的常见坑：a = [5]、b = [3]。

3. 把「不大于」写成「小于」

条件是 max(A) <= min(B)，相等是允许的，所以用 bisect_right 而不是 bisect_left。
把样例 a = [3]、b = [3] 跑一下就能发现：正确答案是 2，不是 -1。

4. 门槛去重取值的范围

不需要遍历 1..10^9 的所有整数（那会超时）。只有数组中出现过的值才会让计数发生变化，
枚举 b 的去重值就够（对称地，枚举 a 的去重值同样能得到正确答案），
配合排序与二分就是 O(n log n)。

---

扩展思考

• 若改成「最大值必须严格小于最小值」，把 bisect_right 换成 bisect_left 即可。
• 若改成「两个子序列长度之和最小」，答案退化成 2（两边各取一个满足条件的元素），
  变成一个双指针判定问题。
• 姊妹题《小O的子序列最值(二)》把「求最大长度」换成了「求方案数」，
  此时要按「最大值恰好为 v」和「最小值恰好为 v」分类计数，再配合前缀和合并。

---

相关题目

• 小O的子序列最值(二)