本文主要是介绍牛客周赛 Round 40(补题)C题,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
链接:登录—专业IT笔试面试备考平台_牛客网
来源:牛客网
题目描述
小红拿到了一个长度为nnn的数组aaa,她希望你构造两个排列ppp和qqq,满足对于i∈[1,n],aii∈[1,n],a_ii∈[1,n],ai为pip_ipi或qiq_iqi二选一。你能帮帮她吗?
定义排列是一个长度为nnn的数组,其中1到nnn每个元素恰好出现1次。
输入描述:
第一行输入一个正整数nnn,代表两个数组的长度。 第二行输入nnn个正整数aia_iai。 1≤n≤1051\leq n \leq 10^51≤n≤105 1≤ai≤n1\leq a_i \leq n1≤ai≤n
输出描述:
如果无解,请输出-1。 否则第一行输出nnn个正整数pip_ipi,第二行输出nnn个正整数qiq_iqi,代表小红构造的两个排列。有多解时输出任意即可。
示例1
输入
复制3 2 3 2
3 2 3 2
输出
复制2 3 1 1 3 2
2 3 1 1 3 2
示例2
输入
复制4 1 1 1 1
4 1 1 1 1
输出
复制-1
-1
解析:
对set不太熟悉。
只需要开启连个set 对其进行查询:
最后 ,只用set *begin()添加进容器中。
#include <bits/stdc++.h>using namespace std;
using ll = long long;
#define N 100000
void solve_case() {int i,j,k,n,m,t,f1[N+50],f2[N+50],a[N+50];set<int> s1,s2;cin >> n;for(int i = 1;i <= n;i++){cin >>a[i];s1.insert(i);s2.insert(i);}for(int i = 1;i <= n;i++){if(s1.count(a[i])){f1[i] = a[i];s1.erase(a[i]);}else if(s2.count(a[i])){f2[i] = a[i];s2.erase(a[i]); } else{cout <<"-1";return;}}for(i = 1;i <= n;i++){if(!f1[i]){f1[i] = *s1.begin();s1.erase(f1[i]);}if(!f2[i]){f2[i] = *s2.begin();s2.erase(f2[i]);}}for(i = 1;i <= n;i++){cout << f1[i]<<" ";}cout<<endl;for(i = 1;i <= n;i++){cout << f2[i]<<" ";}cout<<endl;}int main() {ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int T = 1;//cin >> T;while (T--) {solve_case();}
}
这篇关于牛客周赛 Round 40(补题)C题的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!