目录

• Description
• State
• Input
• Output
• Solution
• Code

Description

要求构造一个长度为 \(n\) 的排列，已知排列中最长上升子序列为 \(k\) ，求字典序最小的排列方式

State

\(1<=n,k<=2*10^{5}\)

\(1<=a[i]<=n\)

Input

3 2
2 3

Output

2 1 3

Solution

不妨猜一下结论，除了最后一个数之外，其余每一个数后面最多再添加一个值

证明：别问，问就是数学归纳

首先有一组数 \(a[1],a[2],a[3]\)， 他们都 \(>3\) ，那么最优解为 \(a[1],1,a[2],2,a[3],3\)，这是显而易见的，那么 \(4\) 就需要分类讨论一下了

1.如果 \(a[1]=4\)， 那么 \(a[2]=5\) 还好说，如果 \(a[2]!=5\)，\(5\) 放在 \(1\) 后面就破坏了上升序列的长度（\(5<a[2]\)）

2.如果 \(a[1]!=4\)， 那么易知 \(4<a[2]\)，仍然不能放在 \(1\) 的后面

最后问题来了，即使 \(a[1],a[2],a[3]\) 都 \(>4\)， \(4\) 该放在哪里呢?

答：\(3\) 的前面，毫无疑问

Code

const int N = 2e5 + 5;

    ll n, m, _;
    int i, j, k;
    ll a[N];
    bool vis[N];

signed main()
{
    //IOS;
    while(~ sdd(n, k)){
        fill(vis, 0);
        rep(i, 1, k){
            sd(a[i]);
        }
        int cur = 1;
        rep(i, 1, k - 1){
            printf("%d ", a[i]);
            vis[a[i]] = 1;
            while(vis[cur]) cur ++;
            if(cur < a[i + 1] && cur < a[i]){
                printf("%d ", cur);
                vis[cur] = 1;
            }
        }
        per(i, 1, n){
            if(! vis[i]) printf("%d ", i);
        }
        puts("");
    }
    //PAUSE;
    return 0;
}