G. Restore the Permutation
A sequence of $n$ numbers is called permutation if it contains all numbers from $1$ to $n$ exactly once. For example, the sequences $[3,1,4,2]$, $[1]$ and $[2,1]$ are permutations, but $[1,2,1]$, $[0,1]$ and $[1,3,4]$ — are not.
For a permutation $p$ of even length $n$ you can make an array $b$ of length $\frac{n}{2}$ such that:
- $b_i = \max(p_{2i - 1}, p_{2i})$ for 1 \le i \le \frac{n}{2}$
For example, if $p = [2,4,3,1,5,6]$, then:
- $b_1 = \max(p_1, p_2) = \max(2, 4) = 4$
- $b_2 = \max(p_3, p_4) = \max(3,1)=3$
- $b_3 = \max(p_5, p_6) = \max(5,6) = 6$
As a result, we made $b = [4,3,6]$.
For a given array $b$, find the lexicographically minimal permutation $p$ such that you can make the given array $b$ from it.
If $b = [4,3,6]$, then the lexicographically minimal permutation from which it can be made is $p = [1,4,2,3,5,6]$, since:
- $b_1 = \max(p_1, p_2) = \max(1, 4) = 4$
- $b_2 = \max(p_3, p_4) = \max(2, 3) = 3$
- $b_3 = \max(p_5, p_6) = \max(5, 6) = 6$
A permutation $x_1, x_2, \ldots, x_n$ is lexicographically smaller than a permutation $x_1, x_2, \ldots, x_n$ if and only if there exists such $i$ $(1 \leq i \leq n)$ that $x_1=y_1,x_2=y_2, \ldots ,x_{i−1}=y_{i−1}$ and $x_i \le y_i$.
Input
The first line of input data contains a single integer $t$ $(1 \leq t \leq {10}^{4})$ — the number of test cases.
The description of the test cases follows.
The first line of each test case contains one even integer $n$ $(2 \leq n \leq 2 \cdot {10}^{5})$.
The second line of each test case contains exactly $\frac{n}{2}$ integers $b_i$ $(1 \leq b_i \leq n)$ — elements of array $b$.
It is guaranteed that the sum of $n$ values over all test cases does not exceed $2 \cdot {10}^{5}$.
Output
For each test case, print on a separate line:
lexicographically minimal permutation $p$ such that you can make an array $b$ from it;
or a number $-1$ if the permutation you are looking for does not exist.
Example
input
6 6 4 3 6 4 2 4 8 8 7 2 3 6 6 4 2 4 4 4 8 8 7 4 5
output
1 4 2 3 5 6 1 2 3 4 -1 5 6 3 4 1 2 -1 1 8 6 7 2 4 3 5
Note
The first test case is parsed in the problem statement.
解题思路
这题容易想到先开个$\text{std::set}$存没出现过的数,然后从前往后枚举数组$b$,在集合中找到小于$b_i$的最小数。但这种做法会存在一个问题,因为每次都是选出最小的数,这导致集合中剩下的数都比较大,这就会导致数组$b$往后的数可能会出现无解的情况,比如现在有数组$b = [6, 4, 2]$,如果按照上面的做法来选择,那么对于$6$则选择$1$,$4$则选择$3$,当枚举到$2$时此时集合中只剩下$5$,而$\max \{ {2, 5} \} = 5$就无解了,但实际上最优解是$[5, 6, 3, 4, 1, 2]$。
根据贪心的思想,对于数组$b$前面的数我们应尽可能匹配小的数,而后面应尽可能匹配大的数,因此为了尽可能保证优解,我们可以从后面往前枚举数组$b$,在集合中找到小于$b_i$的最大数,如果存在的话那么就选择这个数并从集合中删除,否则说明无解。这种做法就为数组$b$前面的数的选择保留了尽可能小的数,一方面尽可能保证字典序最小,另一方面也尽可能保证前面部分能够有解。
AC代码如下:
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 const int N = 2e5 + 10; 5 6 int a[N], ans[N]; 7 8 void solve() { 9 int n; 10 scanf("%d", &n); 11 set<int> st; 12 for (int i = 1; i <= n; i++) { 13 st.insert(i); 14 } 15 for (int i = 1; i <= n >> 1; i++) { 16 scanf("%d", a + i); 17 st.erase(a[i]); 18 } 19 20 if (st.size() != n >> 1) { // 说明给定的序列有重复数字出现,一定无解 21 printf("-1\n"); 22 return; 23 } 24 25 for (int i = n >> 1; i; i--) { 26 ans[i * 2] = a[i]; 27 auto it = st.lower_bound(a[i]); // 先找到大于等于a[i]的最小的数 28 if (it == st.begin()) { // 如果这个数是集合中最小的数,意味着不存在严格小于a[i]的数,无解 29 printf("-1\n"); 30 return; 31 } 32 ans[i * 2 - 1] = *--it; // prev(it)就是小于a[i]的最大的数 33 st.erase(it); 34 } 35 36 for (int i = 1; i <= n; i++) { 37 printf("%d ", ans[i]); 38 } 39 printf("\n"); 40 } 41 42 int main() { 43 int t; 44 scanf("%d", &t); 45 while (t--) { 46 solve(); 47 } 48 49 return 0; 50 }
参考资料
Codeforces Round #834 (Div. 3) A-G:https://www.cnblogs.com/BlankYang/p/16906184.html
标签:Restore,int,max,Permutation,st,leq,permutation,test From: https://www.cnblogs.com/onlyblues/p/16908899.html