CF1893B Neutral Tonality

One_JuRuo · 2023-11-14 14:48:11 · 题解

思路

首先可以知道答案的下界就是序列 a 原来的 LIS，现在需要做的就是尽可能地保持答案不增加。

可以肯定的是，将序列 b 从大到小地插入序列 a 是不劣的，并且如果在 a_i 前插入的都是 \ge a_i 的不会使答案增加，可以感性理解，如果原来的 LIS 没有选择 a_i，那么选择插入的降序序列则会让答案变劣，如果选择了 a_i，并且在插入后改为下降序列的某一个数字，那么后面的选择会变少，答案一定不会增加。

所以这道题就很明了了。

对于 a_i，直接将目前剩下的所有 \ge a_i 的数字按照降序全部在 a_i 前插入即可，还需要将没插完的 b_i 在最后降序输出。

AC code

#include<bits/stdc++.h>
using namespace std;
int T,n,m,a[200005],b[200005],p;
inline bool cmp(int a,int b){return a>b;}
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&m),p=1;
        for(int i=1;i<=n;++i) scanf("%d",&a[i]);
        for(int i=1;i<=m;++i) scanf("%d",&b[i]);
        sort(b+1,b+m+1,cmp);
        for(int i=1;i<=n;++i)
        {
            while(p<=m&&b[p]>=a[i]) printf("%d ",b[p++]);
            printf("%d ",a[i]);
        }
        for(int i=p;i<=m;++i) printf("%d ",b[i]);
        puts("");
    }
    return 0;
}