题解
1.\(LIS(a)\) 已经改变不了了,所以要让插入的 \(b\) 尽量少地增加 \(LIS\) 所以要降序、从左到右插入
2.\(a\) 的相对顺序不变
3.此时已知两个数组的相对顺序,因此我们可以贪心地输出两个数组顶端元素中较大的那个
为什么可以这样?
我们假设输出顶端元素较小的那个,那么 \(LIS(c)\) 可能加一可能不变,并不比输出较大的决策更优
code
#include<bits/stdc++.h>
using namespace std;
int a[200005],b[200005],c[200005];
int suf[400006];
int main()
{
int t;
cin>>t;
while(t--)
{
int n,m;
cin>>n>>m;
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,greater<int>());
int it1=1,it2=1;
while(it1<=n&&it2<=m)
{
if(a[it1]>b[it2]) cout<<a[it1++]<<" ";
else cout<<b[it2++]<<" ";
}
while(it1<=n) cout<<a[it1++]<<" ";
while(it2<=m) cout<<b[it2++]<<" ";
puts("");
}
return 0;
}
标签:200005,int,while,Neutral,LIS,Tonality
From: https://www.cnblogs.com/pure4knowledge/p/18253072