题解 | #小O的子序列最值#

题目链接

题目描述

给定两个长度为 $n$ 的数组 $A$ 和 $B$ 。需要从这两个数组中分别选出一个非空子序列，记为 sub_A 和 sub_B，要求满足 sub_A 的最大值不大于 sub_B 的最小值。目标是使两个子序列的长度之和 len(sub_A) + len(sub_B) 最大。

解题思路

1. 问题转化

为了最大化子序列的长度和，我们应该尽可能多地往子序列里放元素。

假设我们已经确定了 sub_A 的最大值为 max_a，sub_B 的最小值为 min_b，且满足 max_a <= min_b。

为了让 sub_A 最长，我们应该包含原数组 $A$ 中所有小于等于 max_a 的元素。
为了让 sub_B 最长，我们应该包含原数组 $B$ 中所有大于等于 min_b 的元素。

这启发我们可以引入一个“分割值” $v$ ，使得 max_a <= v <= min_b。如果我们固定了这样一个 $v$ ，那么最优策略就是：

sub_A 包含 $A$ 中所有 $\le v$ 的元素。
sub_B 包含 $B$ 中所有 $\ge v$ 的元素。

这样构造的两个子序列自动满足条件，并且长度达到了最大化。因此，原问题就转化为：寻找一个最优的分割值 $v$ ，使得 (A中 <= v 的元素个数) + (B中 >= v 的元素个数) 最大。

2. 寻找最优分割值 $v$

分割值 $v$ 的取值范围看似是无限的，但计数值只在 $v$ 跨越 $A$ 或 $B$ 中某个存在的元素值时才会发生变化。因此，我们只需要把 $A$ 和 $B$ 中所有出现过的唯一值作为 $v$ 的候选集合即可。

一个直接但效率不高的做法是，遍历所有候选值 $v$ ，对每个 $v$ 都扫描一遍数组 $A$ 和 $B$ 来计数，总复杂度为 $\mathcal{O}(N^2)$ ，会超时。

3. 高效算法：坐标离散化 + 前缀/后缀和

我们可以通过预处理来快速计算所有候选值的计数。

离散化: 收集数组 $A$ 和 $B$ 中的所有唯一值，并将它们排序，得到一个有序的候选值列表 vals。
频率统计: 使用 map 或哈希表统计 vals 中每个值在 $A$ 和 $B$ 中各自的出现次数。
计算前缀和与后缀和:
- 对于数组 A: 我们需要 count(A中 <= v 的元素个数)。这可以通过对 $A$ 的频率进行一次前缀和计算得到。我们创建一个 count_A_le 数组，count_A_le[i] 存储 $A$ 中小于等于 vals[i] 的元素总数。
- 对于数组 B: 我们需要 count(B中 >= v 的元素个数)。这可以通过对 $B$ 的频率进行一次后缀和计算得到。我们创建一个 count_B_ge 数组，count_B_ge[i] 存储 $B$ 中大于等于 vals[i] 的元素总数。
寻找最优解: 遍历 vals 列表（长度为 $M \le 2N$ ）。对于每个索引 i，对应的分割值为 vals[i]，此时的子序列长度和为 count_A_le[i] + count_B_ge[i]。我们只需遍历一遍，找到这个和的最大值即可。
注意: 题目要求子序列非空，因此在计算总和时，必须保证 count_A_le[i] 和 count_B_ge[i] 都大于 0。

代码

cpp
java
python

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;
    vector<int> a(n), b(n);
    map<int, int> freq_a, freq_b;
    map<int, int> all_vals_map;

    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        freq_a[a[i]]++;
        all_vals_map[a[i]] = 0;
    }
    for (int i = 0; i < n; ++i) {
        cin >> b[i];
        freq_b[b[i]]++;
        all_vals_map[b[i]] = 0;
    }

    vector<int> vals;
    for (auto const& [val, ignore] : all_vals_map) {
        vals.push_back(val);
    }

    int m = vals.size();
    if (m == 0) {
        cout << 0 << endl;
        return 0;
    }

    vector<long long> count_a_le(m);
    long long current_sum_a = 0;
    for (int i = 0; i < m; ++i) {
        if (freq_a.count(vals[i])) {
            current_sum_a += freq_a[vals[i]];
        }
        count_a_le[i] = current_sum_a;
    }

    vector<long long> count_b_ge(m);
    long long current_sum_b = 0;
    for (int i = m - 1; i >= 0; --i) {
        if (freq_b.count(vals[i])) {
            current_sum_b += freq_b[vals[i]];
        }
        count_b_ge[i] = current_sum_b;
    }

    long long max_len = 0;
    for (int i = 0; i < m; ++i) {
        if (count_a_le[i] > 0 && count_b_ge[i] > 0) {
            max_len = max(max_len, count_a_le[i] + count_b_ge[i]);
        }
    }

    cout << max_len << endl;

    return 0;
}

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;
import java.util.TreeMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        int[] b = new int[n];

        TreeMap<Integer, Integer> freqA = new TreeMap<>();
        TreeMap<Integer, Integer> freqB = new TreeMap<>();
        TreeMap<Integer, Integer> allValsMap = new TreeMap<>();

        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
            freqA.put(a[i], freqA.getOrDefault(a[i], 0) + 1);
            allValsMap.put(a[i], 0);
        }
        for (int i = 0; i < n; i++) {
            b[i] = sc.nextInt();
            freqB.put(b[i], freqB.getOrDefault(b[i], 0) + 1);
            allValsMap.put(b[i], 0);
        }

        List<Integer> vals = new ArrayList<>(allValsMap.keySet());
        int m = vals.size();

        if (m == 0) {
            System.out.println(0);
            return;
        }

        long[] countALe = new long[m];
        long currentSumA = 0;
        for (int i = 0; i < m; i++) {
            currentSumA += freqA.getOrDefault(vals.get(i), 0);
            countALe[i] = currentSumA;
        }

        long[] countBGe = new long[m];
        long currentSumB = 0;
        for (int i = m - 1; i >= 0; i--) {
            currentSumB += freqB.getOrDefault(vals.get(i), 0);
            countBGe[i] = currentSumB;
        }

        long maxLen = 0;
        for (int i = 0; i < m; i++) {
            if (countALe[i] > 0 && countBGe[i] > 0) {
                maxLen = Math.max(maxLen, countALe[i] + countBGe[i]);
            }
        }

        System.out.println(maxLen);
    }
}

import sys
from collections import Counter

def solve():
    n_str = sys.stdin.readline()
    if not n_str:
        return
    n = int(n_str)
    a = list(map(int, sys.stdin.readline().split()))
    b = list(map(int, sys.stdin.readline().split()))

    freq_a = Counter(a)
    freq_b = Counter(b)
    
    vals = sorted(list(set(a) | set(b)))
    m = len(vals)

    if m == 0:
        print(0)
        return

    count_a_le = [0] * m
    current_sum_a = 0
    for i in range(m):
        current_sum_a += freq_a[vals[i]]
        count_a_le[i] = current_sum_a

    count_b_ge = [0] * m
    current_sum_b = 0
    for i in range(m - 1, -1, -1):
        current_sum_b += freq_b[vals[i]]
        count_b_ge[i] = current_sum_b

    max_len = 0
    for i in range(m):
        if count_a_le[i] > 0 and count_b_ge[i] > 0:
            max_len = max(max_len, count_a_le[i] + count_b_ge[i])
            
    print(max_len)

solve()

算法及复杂度

算法: 坐标离散化、前缀和、后缀和
时间复杂度:
- 读取输入并统计频率到 map 中： $\mathcal{O}(N \log N)$ 。
- 提取唯一值并排序：map 的键已经是排序的，提取需要 $\mathcal{O}(M)$ ，其中 $M$ 是唯一值的数量 ( $M \le 2N$ )。
- 计算前缀和与后缀和： $\mathcal{O}(M)$ 。
- 遍历寻找最大值： $\mathcal{O}(M)$ 。
- 因此，总的时间复杂度由 map 操作主导，为 $\mathcal{O}(N \log N)$ 。
空间复杂度:
- 存储输入的数组： $\mathcal{O}(N)$ 。
- map 和 vals 列表： $\mathcal{O}(M)$ 。
- 前缀和、后缀和数组： $\mathcal{O}(M)$ 。
- 因此，总的空间复杂度为 $\mathcal{O}(N)$ 。