题目链接
A permutation is a sequence of n integers from 1 to n, in which all numbers occur exactly once. For example, [1], [3,5,2,1,4], [1,3,2] are permutations, and [2,3,2], [4,3,1], [0] are not.
Polycarp was presented with a permutation p of numbers from 1 to n. However, when Polycarp came home, he noticed that in his pocket, the permutation p had turned into an array q according to the following rule:
qi=max(p1,p2,…,pi).
Now Polycarp wondered what lexicographically minimal and lexicographically maximal permutations could be presented to him.
An array a of length n is lexicographically smaller than an array b of length n if there is an index i (1≤i≤n) such that the first i−1 elements of arrays a and b are the same, and the i-th element of the array a is less than the i-th element of the array b. For example, the array a=[1,3,2,3] is lexicographically smaller than the array b=[1,3,4,2].
For example, if n=7 and p=[3,2,4,1,7,5,6], then q=[3,3,4,4,7,7,7] and the following permutations could have been as p initially:
[3,1,4,2,7,5,6] (lexicographically minimal permutation);
[3,1,4,2,7,6,5];
[3,2,4,1,7,5,6];
[3,2,4,1,7,6,5] (lexicographically maximum permutation).
For a given array q, find the lexicographically minimal and lexicographically maximal permutations that could have been originally presented to Polycarp.
Input
The first line contains one integer t (1≤t≤104). Then t test cases follow.
The first line of each test case contains one integer n (1≤n≤2⋅105).
The second line of each test case contains n integers q1,q2,…,qn (1≤qi≤n).
It is guaranteed that the array q was obtained by applying the rule from the statement to some permutation p.
It is guaranteed that the sum of n over all test cases does not exceed 2⋅105.
Output
For each test case, output two lines:
on the first line output n integers — lexicographically minimal permutation that could have been originally presented to Polycarp;
on the second line print n integers — lexicographically maximal permutation that could have been originally presented to Polycarp;
题意：有一个数组a,长度为n，a的元素是1-n中每一个数组成，现给定b数组，
b
i
b_i
b
i
等于
m
a
x
(
a
1
,
a
2
,
a
3
.
.
.
a
i
)
max(a_1,a_2,a_3…a_i)
m
a
x
(
a
1
,
a
2
,
a
3
.
.
.
a
i
)
，求a数组字典序最小的排列和字典序最大的排列
思路：我们可以根据b数组确定一些a数组元素，字典序最小的通过从小到大填补空缺即可，字典序最大的用set二分查找逐步填入就行
#include<bits/stdc++.h>
#define ll long long
using namespace std;
void slove()
{
int n;cin>>n;
int a[n+5];
int maxans[n+5];
int minans[n+5];
map<int,int>mp;
set<int>s;
vector<int>v;
memset(maxans,-1,sizeof maxans);
memset(minans,-1,sizeof minans);
for(int i=0;i<n;i++)
cin>>a[i],mp[a[i]]=1;
for(int i=1;i<=n;i++)
{
if(mp[i]==0)
{
s.insert(i);
v.push_back(i);
}
}
//cout<<s.size()<<endl;
// for(auto p=s.begin();p!=s.end();++p)
// cout<<*p<<endl;
maxans[0]=a[0];
minans[0]=a[0];
for(int i=1;i<n;i++)
{
if(a[i]!=a[i-1])
{
maxans[i]=a[i];
minans[i]=a[i];
}
}
int f=0;
for(int i=1;i<n;i++)
{
if(maxans[i]==-1)
{
maxans[i]=v[f];
f++;
}
}
// for(int i=0;i<n;i++)
// cout<<minans[i]<<" ";
//cout<<endl;
for(int i=1;i<n;i++)
{
if(minans[i]==-1)
{
if(s.size()==0) break;
auto p=--s.upper_bound(minans[i-1]);
minans[i]=*p;
//cout<<*p<<" "<<minans[i]<<endl;
s.erase(p);
//for(auto u=s.begin();u!=s.end();++u)
// cout<<*u<<" ";
// cout<<endl;
}
}
for(int i=0;i<n;i++)
cout<<maxans[i]<<" ";
cout<<endl;
for(int i=0;i<n;i++)
cout<<minans[i]<<" ";
cout<<endl;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;cin>>t;
while(t--)
slove();
return 0;
}