codeforce每日一题汇总链接
题目链接
题目分数:1900
题目描述
输入$T(≤1e4)$表示$T$组数据。所有数据的$n$之和$≤2e5$。每组数据输入偶数$n(2≤n<=2e5)$和长为$n/2$的数组$b(1≤b[i]<=n)$,下标从$1$开始。构造一个长为$n$的$1-n$ 的排列$p$(下标从$1$开始),满足$max(p[2*i-1],p[2*i])=b[i]$。如果无法构造,输出$-1$,否则输出字典序最小的$p$。
样例
输入样例1
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
输出样例1
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
算法
(枚举+构造) $O(n)$
这道题首先可以发现,如果b数组中出现了相同的数字,就一定无法构造出来。又发现,因为需要构造的序列是一个$1-n$的排列,所以每一个$b[i]$都会有一个小于它的数字,以组合成$p[2*i],p[2*i+1]$,所以在$1-k$中,$b$数组在这个范围内出现的数字一定要小于可以搭配的数字个数,否则无解。
然后我们就可以开始构造了,我们可以从大到小枚举数字,对于没有在$b$中出现过的数字,我们需要填到$b$中大于当前数字且在构造的数组中最靠后的数字前面。所以代码可以这样写,如果当前数字在$b$中出现过,就把它在构造的数组中位置放到大根堆里,如果没有出现过,我们就从大根堆里拿出一个元素,并删除它,把当前枚举的数字放到拿出的元素前面。我们可以证明,如果交换顺序,那么一定是较大的数字被交换到了前面,所以答案一定会变差。
C++ 代码
#include<bits/stdc++.h>
#define fi first
#define se second
#define all(a) a.begin(), a.end()
#define pd push_back
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
typedef pair<double, double> PDD;
const int N = 2e5 + 10, M = N * 2, INF = 0x3f3f3f3f;
int n, m;
int w[N], res[N];
int st[N];
inline void solve()
{
memset(st, 0, sizeof st);
unordered_map<int,int> ha;
cin>>n;
for(int i=1;i<=n/2;++i) cin>>w[i], st[w[i]]++, res[i*2] = w[i], ha[w[i]] = i * 2;
for(int i=1,sum=0;i<=n;i++){
if(st[i]>1){
cout<<-1<<endl;
return;
}
if(st[i]) sum++;
if(sum>i-sum){
cout<<-1<<endl;
return;
}
}
priority_queue<int> heap;
for(int i=n;i;--i){
if(st[i]){
heap.push(ha[i]);
}else{
res[heap.top()-1] = i;
heap.pop();
}
}
for(int i=1;i<=n;i++) cout<<res[i]<<" ";
cout<<endl;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int T;
cin>>T;
while(T--)
{
solve();
}
return 0;
}