题目 | Neutral Tonality
Codeforces Round 908 (Div. 2)
D. Neutral Tonality
https://codeforces.com/contest/1894/problem/D
3 seconds / 512 megabytes
standard input / standard output
Problem
You are given an array
Let
You need to insert the numbers
Formally, you need to find an array
- The array
is a subsequence of the array . - The array
consists of the numbers , possibly rearranged. - The value of
is the minimum possible among all suitable arrays .
Input
Each test contains multiple test cases. The first line contains a single integer
The first line of each test case contains two integers
The second line of each test case contains
The third line of each test case contains
It is guaranteed that the sum of
Output
For each test case, output
Example
Input
7
2 1
6 4
5
5 5
1 7 2 4 5
5 4 1 2 7
1 9
7
1 2 3 4 5 6 7 8 9
3 2
1 3 5
2 4
10 5
1 9 2 3 8 1 4 7 2 9
7 8 5 4 6
2 1
2 2
1
6 1
1 1 1 1 1 1
777
Output
6 5 4
1 1 7 7 2 2 4 4 5 5
9 8 7 7 6 5 4 3 2 1
1 3 5 2 4
1 9 2 3 8 8 1 4 4 7 7 2 9 6 5
2 2 1
777 1 1 1 1 1 1
Note
In the first test case,
In the second test case,
题解
首先需要注意到,将
最基本的,我们插入的序列必须是降序的,如此能保证插入的
接下来,若插入的值与原序列形成的都是降序段,则不会使
因此,这道题的最优解实际上
代码实现上其实非常简单,和归并排序的合并过程是一样的写法。
代码
#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
void solve()
{
int n, m;
cin >> n >> m;
vector<int> a(n), b(m);
for (int i = 0; i < n; i++)
cin >> a[i];
for (int i = 0; i < m; i++)
cin >> b[i];
sort(b.begin(), b.end(), greater<int>());
int i = 0, j = 0;
while (i < n && j < m)
{
if (a[i] <= b[j])
cout << b[j++] << ' ';
else
cout << a[i++] << ' ';
}
for (; i < n; i++)
cout << a[i] << ' ';
for (; j < m; j++)
cout << b[j] << ' ';
cout << endl;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t = 1;
cin >> t;
while (t--)
solve();
return 0;
}
本文采用 CC BY-SA 4.0 许可,本文 Markdown 源码:Haotian-BiJi