题目描述
小红拿到了一个长度为n的数组a，她希望你构造两个排列p和q，满足对于i∈[1,n],ai∈[1,n]pi或qi二选一。你能帮帮她吗？定义排列是一个长度为n的数组，其中1到n每个元素恰好出现1次。
输入描述:第一行输入一个正整数n，代表两个数组的长度。 第二行输入n个正整数ai。1≤n≤10^5,1≤ai≤n。
输出描述:如果无解，请输出-1。 否则第一行输出n个正整数pi，第二行输出n个正整数qi，代表小红构造的两个排列。有多解时输出任意即可。
输入
3
2 3 2
输出
2 3 1
1 3 2
输入
4
1 1 1 1
输出：-1
#include<bits/stdc++.h> #include<iostream> #include<vector> using namespace std; const long long N=1e7+5; inline int read(){//内联函数效率更高 int x=0,f=1; char c=getchar(); while(c<'0'||c>'9') { if(c=='-') f=-1; c=getchar(); } while(c>='0'&&c<='9'){ x=(x<<1)+(x<<3)+(c^48),c=getchar(); } return x*f; } inline void print(int x) { if(x<0) putchar('-'),x=-x; if(x>9) print(x/10); putchar(x%10+'0'); return;} int n,k=0,z=0; vector<int> tr(N),arr(N),p1(N),p2(N);//向量比数组更加灵活与方便 int main(){ cin>>n; for(int i=1;i<=n;i++){ arr[i]=read(); if(tr[arr[i]]==2){ cout<<"-1"; return 0; } ++tr[arr[i]]; } for(int i=1;i<=n;i++){ if(tr[arr[i]]==1){ p1[i]=arr[i]; p2[i]=arr[i]; } if(tr[arr[i]]==3){ while(tr[++k]!=0); p1[i]=k; p2[i]=arr[i]; } if(tr[arr[i]]==2){ tr[arr[i]]=3; p1[i]=arr[i]; while(tr[++z]!=0); p2[i]=z; } } for(int i=1;i<=n;i++)print(p1[i]),putchar(32); putchar(10); for(int i=1;i<=n;i++)print(p2[i]),putchar(32); putchar(10); return 0; }
这个虽然通过运行但是时间和内存都耗费很大
#include<bits/stdc++.h> #define ll long long const ll N=1e5+5; #define _for(i,a,b) for(int(i)=(a);(i)<(b);(i)++) using namespace std; inline int read(){ int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-')f=-1;ch=getchar(); } while(ch>='0'&&ch<='9'){ x=(x<<1)+(x<<3)+(ch^48),ch=getchar(); } return x*f; } void write(int x) { if(x<0)putchar('-'),x=-x; if(x>9) write(x/10); putchar(x%10+'0'); return;} int n,k=0,z=0; vector<int> tr(N),arr(N),p1(N),p2(N); int main(){ cin>>n; for(int i=1;i<=n;i++){ arr[i]=read(); if(tr[arr[i]]==2){ cout<<"-1"; return 0; } ++tr[arr[i]]; } for(int i=1;i<=n;i++){ if(tr[arr[i]]==1){ p1[i]=arr[i]; p2[i]=arr[i]; } if(tr[arr[i]]==3){ while(tr[++k]!=0); p1[i]=k; p2[i]=arr[i]; } if(tr[arr[i]]==2){ tr[arr[i]]=3; p1[i]=arr[i]; while(tr[++z]!=0); p2[i]=z; } } for(int i=1;i<=n;i++)write(p1[i]),putchar(32); putchar(10); for(int i=1;i<=n;i++)write(p2[i]),putchar(32); putchar(10); return 0; }
原因如下：
第一次定义的数组范围过大，造成无用空间过多的浪费；
#define _for(i,a,b) for(int(i)=(a);(i)<(b);(i)++)类似于定义了一个模板，效率更高。
n用于存储整数的数量；k和z用于临时存储新的整数值；tr数组记录每个整数出现的次数；arr数组存储原始整数序列；p1和p2数组分别存储变换后的两个序列；- 读取整数序列，统计每个整数出现的次数并存储在
tr数组中； - 遍历
arr数组，根据tr[arr[i]]的值决定如何填充p1和p2： - 如果某个整数出现了4次，先将其置为3次，然后分别将它放入
p1和一个新的未出现过的整数放入p2。 - 如果某个整数出现了偶数次但不是4次，将其中一个放入
p1，然后找一个未出现过的整数放入p2； - 如果某个整数出现了奇数次，直接放入两个新数组；
- 最后输出处理后的两个序列
