题目描述

难度分:$1700$

输入$T(\leq 10^4)$表示$T$组数据。所有数据的$n$之和$\leq 2 \times 10^5$，$m$之和$\leq 2 \times 10^5$。

每组数据输入$n(1 \leq n \leq 2 \times 10^5)$，$m(1 \leq m \leq 2 \times 10^5)$和长为$n$的数组$a(1 \leq a[i] \leq 10^9)$，长为$m$的数组$b(1 \leq b[i] \leq 10^9)$。

把$b$中所有元素以任意顺序在任意位置插入$a$中，得到数组$c$。例如$a=[3,1,1]$，$b=[9,4,5]$，插入后可以是$c=[3,1,4,1,5,9]$。

你需要使$LIS(c)$最短（$LIS$是最长严格递增子序列），输出任意符合要求的$c$。

输入样例

7
2 1
6 4
5
5 5
1 7 2 4 5
5 4 1 2 7
1 9
7
1 2 3 4 5 6 7 8 9
3 2
1 3 5
2 4
10 5
1 9 2 3 8 1 4 7 2 9
7 8 5 4 6
2 1
2 2
1
6 1
1 1 1 1 1 1
777

输出样例

6 5 4
1 1 7 7 2 2 4 4 5 5
9 8 7 7 6 5 4 3 2 1
1 3 5 2 4
1 9 2 3 8 8 1 4 4 7 7 2 9 6 5
2 2 1
777 1 1 1 1 1 1

算法

贪心构造

挺有思维难度的一道题，代码很短，但是需要好好思考。首先可以明确的是，由于$a$不让动，所以$c$的$LIS$是绝对不可能比$a$短的，不要抱有这个不切实际的幻想。那么我们就希望把$b$的元素插入到$a$后，$LIS$的增量最小，那必然存在一个最优解是把$b$降序排列后按顺序插入到$a$的元素间隙中去。

接下来就比较直觉了，对于一个递增序列中的某个元素$num$，我们肯定是希望把比它大的元素按照降序插入在它前面，这样增加的就是降序的长度，不会增加$num$所在递增序列的长度。所以$i$指针遍历$a$，同时$j$指针遍历降序的$b$，对于某个元素$a[i]$，先往$c$数组中追加大于$a[i]$的$b[j]$，右移$j$指针（如果$b$还没有遍历完的话），然后再追加$a[i]$，右移$i$指针。遍历完$a$数组后，如果$b$还没有遍历完，就继续把剩余元素追加到$c$中。

复杂度分析

时间复杂度

对$b$排序的时间复杂度为$O(mlog_2m)$，然后构造$c$数组是个双指针算法，遍历完了$a$数组和$b$数组，时间复杂度为$O(n+m)$。因此，整个算法的时间复杂度为$O(mlog_2m+n+m)$。

空间复杂度

$c$这个答案数组的空间是可以省掉的，可以在双指针的运行过程中直接打印。因此算法的空间瓶颈在于排序，以快排为基准，额外空间复杂度就是$O(log_2m)$。如果是堆排序，额外空间复杂度可以是$O(1)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
int t, n, m, num;

int main() {
    scanf("%d", &t);
    for(int cases = 1; cases <= t; cases++) {
        scanf("%d%d", &n, &m);
        vector<int> a, b;
        for(int i = 0; i < n; i++) {
            scanf("%d", &num);
            a.push_back(num);
        }
        for(int i = 0; i < m; i++) {
            scanf("%d", &num);
            b.push_back(num);
        }
        sort(b.begin(), b.end());
        int j = m - 1;
        for(int i = 0; i < n; i++) {
            while(j >= 0 && b[j] > a[i]) {
                printf("%d ", b[j--]);
            }
            printf("%d ", a[i]);
        }
        while(j >= 0) {
            printf("%d ", b[j--]);
        }
        puts("");
    }
    return 0;
}