ARC 125 C - LIS to Original Sequence (贪心+思维)

链接

题意：

给出你n个数[1~n],然后给出其最长递增子序列，长度为k， 之后是其最长递增子序列。让你构造出长度为n包括 [1 ~ n], 并且最长递增子序列是给出的。并且字典序最小。

分析：

我们肯定想是构造出来这个最长递增子序列，那么

我们认为这样是最优的，其实不然。例如

​

​10 3​

​​

​2 5 8​

​

如果我们按上面的来，答案应该是​

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

​

但是其实我们还可以这样：

10 3 
2 5 8
第一种方式答案：2 1 5 4 3 10 9 8 7 6
第二种方式答案：2 1 5 3 10 9 8 7 6 4      

ll n, m,cnt;
ll a[maxn], b[maxn],c[maxn];
void solve()
{
    scanf("%lld%lld", &n, &m);
    for(int i = 1; i <= m; i++)
    {
        scanf("%lld", &a[i]);
        b[a[i]]=1;
    }
    for(int i=1;i<=n;i++){
        if(b[i]) continue;
        else c[++cnt]=i;
    }
    ll num=1;
    for(int i=1;i<m;i++){
        cout<<a[i]<<" ";
        if(num<=cnt&&c[num]<a[i]) cout<<c[num++]<<" "; 
    }
    while(cnt>=num&&c[cnt]>a[m]) cout<<c[cnt--]<<" ";
    cout<<a[m]<<" ";
    while(cnt>=num) cout<<c[cnt--]<<" ";
}