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;
}