思路
题意这里就不讲了,直接进入正题。
贪心。
首先我们知道要想尽可能的让每一次操作都合法就得使 \(k\) 最大化,那么要使 \(k\) 最大就得尽可能的选择 \(0\) 操作,所以贪心策略就出来了:优先选择 \(0\) 操作,\(A,B\) 序列那个有 \(0\) 就选哪个合并。如果两个序列当前都没有 \(0\),就需要进行判断了:
- 如果 \(k\) 比 \(A\) 序列当前的数和 \(B\) 序列当前的数都小一定无解(想想为什么)。
- 否则在 \(A,B\) 序列当前的中选择比 \(k\) 小的进行合并。
其余细节将在注释中呈现。
代码
#include<bits/stdc++.h>
using namespace std;
int t,a[105],b[105],c[205];//c数组表示合并后序列
int k,m,n;
bool ok;
int main(){
cin>>t;
while(t--){
int cnt=0;
ok=0;
scanf("%d%d%d",&k,&n,&m);
for(int i=1;i<=n;++i){
scanf("%d",&a[i]);
}
for(int i=1;i<=m;++i){
scanf("%d",&b[i]);
}
a[n+1]=b[m+1]=0x3f3f3f3f;//赋为极大值防止在合并时将多余的0加入序列
int l=1,r=1;//l,r分别表示A序列和B序列当前数的位置
while(l<=n||r<=m){
if(a[l]==0){
c[++cnt]=0;
l++;
k++;
}
else if(b[r]==0){
c[++cnt]=0;
r++;
k++;
}//贪心的合并两序列
else{
if(k<a[l]&&k<b[r]){//如果k比A,B序列当前数都小即无解
puts("-1");
ok=1;
break;
}
if(k>=a[l])c[++cnt]=a[l],l++;//否则正常合并
else if(k>=b[r])c[++cnt]=b[r],r++;
}
}
if(!ok){
for(int i=1;i<=cnt;++i)cout<<c[i]<<" ";
puts("");
}
}
return 0;
}
完结撒花~~。