D. Neutral Tonality-Codeforces Round 908 (Div. 2)

本文主要是介绍D. Neutral Tonality-Codeforces Round 908 (Div. 2)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

D. Neutral Tonality

题意：给出两个数组，将第二个数组插入第一个数组，让插入后的数组LIS最小。

复习：LIS-最大上升序列

解决LIS问题使用的方法是dp
dp[i]表示选中第i位，取前i位的最大上升序列的长度
代码如下：

/*不是本题的答案*/
#include<iostream>
using namespace std;
int main()
{int n;cin>>n;int a[n+2];int dp[n+2];for(int i=1;i<=n;i++){cin>>a[i];}for(int i=1;i<=n;i++){//遍历每一位数dp[i]=1;for(int j=1;j<i;j++){//找这个数前面比他小的数，那么这位dp就是上位dp+1（或不变，取最大值）if(a[i]>a[j]){dp[i]=max(dp[i],dp[j]+1);}}}int ans=0;for(int i=1;i<=n;i++){//再次遍历，找到最大的dp输出。ans=max(ans,dp[i]);}cout<<ans<<endl;
}

分析：

那么对于这道题来说，我们并不需要算出LIS的值，题目要求输出合并后的新数组。
那么如何插入能够使得LIS尽量小呢？
降序数组的LIS是最小的，比如5 4 3 2 1这组数的LIS=0；
所以可以将b数组降序插入，首先对b数组降序排序，遍历a数组，对于每一个元素a[i]，在这个元素之前插入比a[i]大的所有降序的b数组元素。
代码如下：

#include<iostream>
#include<algorithm>
using namespace std;
bool cmp(int a,int b){return a>b;
}
int main()
{int T;cin>>T;while(T--){int n,m;cin>>n>>m;int a[n+2],b[m+2];for(int i=1;i<=n;i++) cin>>a[i];for(int i=1;i<=m;i++) cin>>b[i];sort(b+1,b+1+m,cmp);// for(int i=1;i<=m;i++) cout<<b[i]<<" ";int pos=1;//数组b的下标for(int i=1;i<=n;i++){while(pos<=m&&b[pos]>a[i]){cout<<b[pos++]<<" ";}cout<<a[i]<<" ";}while(pos<=m){//处理剩余的b数组元素cout<<b[pos++]<<" ";}cout<<endl;}
}