本文主要是介绍1759G-Restore the Permutation，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：Restore the Permutation
题目要求字典序最小，因此我们贪心的考虑，假设b数组为 4 3 6，那么我们贪心的考虑得到的结果是 1 4 2 3 5 6 ，但是如果b数组是8 7 4 5 那么我们不能够是1 8 2 7 3 4 6 5，因为最后一个数明显不符合。
因此我们从后往前枚举，寻找第一个比这个数小的数，然后删除这个数，因此我们可以采用lower_bound()函数来寻找第一个比它小的数，用vector记录除了选择的数，如果这个数被选，那么就erase。
那么什么情况下是-1呢？当然只有从后往前枚举的时候剩余的数不能找到和它匹配的数，也就是说没有比它小的数了，那么我们可以从1到n遍历，判断枚举到i时b数组中的数枚举到的数的个数和没有在b数组的个数，再进行比较即可。
代码附上：
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5+5;
int a[N];
int n;
int top=0;
vector<int>b;
int ans[N];
int vis[N];void solve(){cin>>n;top=0;b.clear();for(int i=0;i<=n;i++)vis[i]=0;for(int i=1;i<=n/2;i++)cin>>a[i];for(int i=1;i<=n/2;i++){if(!vis[a[i]])vis[a[i]]=1;else {cout<<-1<<"\n";return;}} int c1=0,c2=0;for(int i=1;i<=n;i++){if(!vis[i]){b.push_back(i);c1++;}else {c2++;if(c1<c2){cout<<-1<<"\n";return;}}}sort(b.begin(),b.end());for(int i=n/2;i>=1;i--){int p=lower_bound(b.begin(),b.end(),a[i])-b.begin()-1;ans[i]=b[p];b.erase(b.begin()+p);}for(int i=1;i<=n/2;i++){cout<<ans[i]<<" "<<a[i]<<" ";}cout<<"\n";}signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int t;cin>>t;while(t--){solve();}return 0;
}这篇关于1759G-Restore the Permutation的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
