小O的子序列最值

[题目链接](https://www.nowcoder.com/practice/c7e5b649799845dca44b2f9ba0f02177)

题意

给定两个长度为 的数组 和 ，从 和 中各选一个非空子序列，要求 所选子序列的最大值不大于 所选子序列的最小值。求两个子序列长度之和的最大值。若无法找到满足条件的选法，输出 。

思路

枚举阈值

设"阈值"为 ，表示第一个子序列的最大值（即 ，同时 ）。

对于给定阈值 ：

• 第一个子序列中可以选 中所有 的元素，全选最优，数量为 。
• 第二个子序列中可以选 中所有 的元素，全选最优，数量为 。
• 两者均非空时，该阈值下的答案为 。

关键观察：最优阈值 一定是 或 中某个元素的值。因此，枚举所有 和 中的元素作为阈值，对每个阈值用二分查找计算 和 ，取合法情况的最大值。

算法

1. 将 、 分别排序。
2. 对 中每个元素 ：

- （ 中 的元素个数）

- （ 中 的元素个数）

- 若 且 ，更新答案。

1. 对 中每个元素 同样处理。
2. 若答案始终为 ，说明无合法选法。

复杂度

排序 ，枚举 。总体 。

示例验证

输入：

4
1 2 3 4
3 4 5 6

排序后 ，。

枚举 （ 中元素）：

• （ 中 的有 ）
• （ 中 的有 ）
• 总和

枚举 ：，，总和 。

最大值为 ，与期望一致。

代码

C++

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

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

    int n;
    cin >> n;

    vector<int> a(n), b(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < n; i++) cin >> b[i];

    sort(a.begin(), a.end());
    sort(b.begin(), b.end());

    int ans = -1;

    for (int i = 0; i < n; i++) {
        int v = a[i];
        int cnt1 = (int)(upper_bound(a.begin(), a.end(), v) - a.begin());
        int cnt2 = (int)(b.end() - lower_bound(b.begin(), b.end(), v));
        if (cnt1 >= 1 && cnt2 >= 1) {
            ans = max(ans, cnt1 + cnt2);
        }
    }

    for (int i = 0; i < n; i++) {
        int v = b[i];
        int cnt1 = (int)(upper_bound(a.begin(), a.end(), v) - a.begin());
        int cnt2 = (int)(b.end() - lower_bound(b.begin(), b.end(), v));
        if (cnt1 >= 1 && cnt2 >= 1) {
            ans = max(ans, cnt1 + cnt2);
        }
    }

    cout << ans << "\n";

    return 0;
}

Java

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine().trim());

        int[] a = new int[n];
        int[] b = new int[n];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) a[i] = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) b[i] = Integer.parseInt(st.nextToken());

        Arrays.sort(a);
        Arrays.sort(b);

        int ans = -1;

        for (int i = 0; i < n; i++) {
            int v = a[i];
            int cnt1 = upperBound(a, v);
            int cnt2 = n - lowerBound(b, v);
            if (cnt1 >= 1 && cnt2 >= 1) {
                ans = Math.max(ans, cnt1 + cnt2);
            }
        }

        for (int i = 0; i < n; i++) {
            int v = b[i];
            int cnt1 = upperBound(a, v);
            int cnt2 = n - lowerBound(b, v);
            if (cnt1 >= 1 && cnt2 >= 1) {
                ans = Math.max(ans, cnt1 + cnt2);
            }
        }

        System.out.println(ans);
    }

    static int upperBound(int[] arr, int v) {
        int lo = 0, hi = arr.length;
        while (lo < hi) {
            int mid = (lo + hi) / 2;
            if (arr[mid] <= v) lo = mid + 1;
            else hi = mid;
        }
        return lo;
    }

    static int lowerBound(int[] arr, int v) {
        int lo = 0, hi = arr.length;
        while (lo < hi) {
            int mid = (lo + hi) / 2;
            if (arr[mid] < v) lo = mid + 1;
            else hi = mid;
        }
        return lo;
    }
}