[数据结构与算法]【题解】ARC125 C - LIS to Original Sequence

题意：构造一个排列 $p$ ，使得 $p$ 的其中一个 LIS 为给定的序列 $a$ 。保证 $a$ 单调递增。

solution:
考点：数学归纳法。
我写的伪贪心 hhh。
如果 k=1 ，那么只有唯一的构造方案 n, n-1, …, 1
考虑从左往右构造，保证字典序最小。设当前全局最小值为 Min 。

1. 如果 a[j]=Min ，那么直接赋 c[i]=a[j++]
2. 否则的话，赋 c[i]=a[j++]，c[i+1]=Min (注意两个一定要一起赋，待会讲为什么)

首先可以知道一定不存在比这种方案更优的答案。我们只需要证明满足条件即可。可以用递归证明，每次的 LIS 长度一定是上一层 + 1 。所以到了 i=1 一定满足 LIS 长度为 k 。
顺带提一句，这个构造方案不是唯一的。