题目描述

难度分:$1998$

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

你需要从$a$的前$n$个数中删除一些数，删除$a[i]$会把$a[i+n]$也一并删除。

你不能把整个数组都删掉。

设删除后的数组为$a’$。

输出字典序最小的$a’$。

输入样例$1$

3
2 1 3 1 2 2

输出样例$1$

1 2

输入样例$2$

10
38 38 80 62 62 67 38 78 74 52 53 77 59 83 74 63 80 61 68 55

输出样例$2$

38 38 38 52 53 77 80 55

输入样例$3$

12
52 73 49 63 55 74 35 68 22 22 74 50 71 60 52 62 65 54 70 59 65 54 60 52

输出样例$3$

22 22 50 65 54 52

算法

单调栈+分类讨论

灵佬表示遇到这种最小字典序的题目，可以往单调栈方向来思考。用单调栈可以求出原数组$a$前$n$个元素的最小字典序结果，此时后面$n$个元素也是确定的。假设前$n$个元素的最小字典序结果为数组$x$，后$n$个元素的对应结果为$y$，接下来就看看$x+y$还能不能更小。

$mn$是所有$y[i]$中的最小值，其中$i$满足$x[i]=x[0]$，即$x[0]$构成的子数组范围所对应的$y[i]$最小值。根据$mn$的值分以下两种情况讨论：

1. $mn \leq x[0]$，例如$x=[2,2,3,3]$，$y=[3,1,2,4]$，此时只需要保留$x[1]$和$y[1]$即可，得到序列$[2,1]$。
2. $mn \gt x[0]$，又有两种情况：$(1)$ $x=[2,2,2,4,4,5,6]$，$y=[4,3,…]$，此时不管$…$是什么，都可以把$x[3:]$全部去掉，得到字典序更小的序列$x+y$。$(2)$ $x=[2,2,2,4,4,5,6]$，$y=[4,7,…]$，此时不管$…$是什么，需要把$x[5:]$去掉才能得到字典序更小的序列$x+y$（至于为什么，从这个例子上看是不言而喻的）。

因此答案就是以上两种情况中字典序更小的那个。

复杂度分析

时间复杂度

利用单调栈求取$x$和$y$的时间复杂度是$O(n)$的，$x$和$y$一定是单调不减的，因此可以用二分来确定$x[i]=x[0]$的范围，时间复杂度为$O(log_2n)$，求得$mn$的时间复杂度又是$O(n)$。接下来分情况讨论，瓶颈在于情况二，求得两个候选序列的时间复杂度是$O(n)$的，比较它们两个的字典序也是$O(n)$的。综上，算法整体的时间复杂度为$O(n)$。

空间复杂度

空间的瓶颈就在于栈空间，以及情况二下的两种候选结果，空间消耗都是$O(n)$级别的。因此，额外空间复杂度为$O(n)$。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;
const int N = 200010;
int n, a[N];

int main() {
    scanf("%d", &n);
    for(int i = 1; i <= 2*n; i++) {
        scanf("%d", &a[i]);
    }
    vector<int> x, y;
    for(int i = 1; i <= n; i++) {
        int j = i + n;
        while(!x.empty() && x.back() > a[i]) {
            x.pop_back();
            y.pop_back();
        }
        x.push_back(a[i]);
        y.push_back(a[j]);
    }
    int i = upper_bound(x.begin(), x.end(), x[0]) - x.begin();
    int mn = y[0];
    for(int j = 0; j < i; j++) {
        mn = min(mn, y[j]);
    }
    if(mn < x[0]) {
        printf("%d %d\n", x[0], mn);
        exit(0);
    }
    int l = lower_bound(x.begin(), x.end(), y[0]) - x.begin();
    int r = upper_bound(x.begin(), x.end(), y[0]) - x.begin();
    vector<vector<int>> cands(2);
    for(int i = 0; i < l; i++) {
        cands[0].push_back(x[i]);
    }
    for(int i = 0; i < l; i++) {
        cands[0].push_back(y[i]);
    }
    for(int i = 0; i < r; i++) {
        cands[1].push_back(x[i]);
    }
    for(int i = 0; i < r; i++) {
        cands[1].push_back(y[i]);
    }
    sort(cands.begin(), cands.end());
    for(int i = 0; i < cands[0].size(); i++) {
        printf("%d ", cands[0][i]);
    }
    puts("");
    return 0;
}