企业官网建设流程全解析

小红的排列构造

时间限制：1 秒
空间限制：256 MB

网页链接

牛客tracker

牛客tracker & 每日一题，完成每日打卡，即可获得牛币。获得相应数量的牛币，能在【牛币兑换中心】，换取相应奖品！助力每日有题做，丰盈牛币日益多！

题目描述

小红拿了一个长度为n nn的数组a aa，她希望你构造两个排列p pp和q qq，满足对于i ∈ [ 1 , n ] i \in [1, n]i∈[1,n]，a i a_iai​为p i p_ipi​或q i q_iqi​二选一。你能帮帮她吗？

定义排列是一个长度为n nn的数组，其中1 11到n nn每个元素恰好出现1 11次。

输入描述

第一行输入一个正整数n nn，代表两个数组的长度。

第二行输入n nn个正整数a i a_iai​。

数据范围：1 ≤ n ≤ 10 5 1 \le n \le 10^51≤n≤105，1 ≤ a i ≤ n 1 \le a_i \le n1≤ai​≤n。

输出描述

如果无解，请输出− 1 -1−1。

否则第一行输出n nn个正整数p i p_ipi​，第二行输出n nn个正整数q i q_iqi​，代表小红构造的两个排列。有多解时输出任意即可。

示例 1

输入：

3 2 3 2

输出：

2 3 1 1 3 2

示例 2

输入：

4 1 1 1 1

输出：

-1

解题思路

本题是排列构造问题，要求根据给定的数组a aa构造两个1 ∼ n 1\sim n1∼n的排列p pp和q qq，使得对于每个位置i ii，p i p_ipi​或q i q_iqi​中至少有一个等于a i a_iai​。需要判断是否有解，并输出任意一组解。

1. 问题等价转化

• 对于每个a i a_iai​，必须满足p i = a i p_i = a_ipi​=ai​或q i = a i q_i = a_iqi​=ai​（或两者都等于）。
• 若某个值x xx在数组a aa中出现次数超过2 22次，则不可能构造成功，因为每个值在两个排列中总共最多出现两次（每个排列各一次）。因此出现次数c n t [ x ] > 2 cnt[x] > 2cnt[x]>2时无解。
• 我们只需关注每个值出现0 , 1 , 2 0,1,20,1,2次的情况，并利用排列的性质（每个数恰好使用一次）进行填充。

2. 构造策略

设pos[x]记录值x xx在数组a aa中的所有下标。

• 出现2 22次的值x xx：假设它出现在位置i ii和j jj。我们可以令p i = x p_i = xpi​=x，q j = x q_j = xqj​=x，这样两个位置都满足了条件。此时在位置i ii的q i q_iqi​还未确定，位置j jj的p j p_jpj​还未确定，它们将成为“自由槽”，需要填入那些在a aa中出现0 00次的值。
• 出现1 11次的值x xx：它只出现在位置i ii，我们可以直接令p i = q i = x p_i = q_i = xpi​=qi​=x，这样该位置一定满足条件，且不占用其他位置。
• 出现0 00次的值y yy：这些值没有直接出现在a aa中，但它们必须分别出现在p pp和q qq的各一个位置。我们可以将它们填入上述“自由槽”中。每个出现2 22次的值会制造两个自由槽（一个在p pp的某个位置，一个在q qq的某个位置），而出现0 00次的值也需要在两个排列中各出现一次，因此二者的数量是匹配的：每两个出现2 22次的值对应两个出现0 00次的值（因为总出现次数守恒）。通过将零数值依次填入自由槽，即可保证每个数字在每个排列中恰好出现一次。

3. 算法步骤

1. 读入n nn和数组a aa，统计每个值x xx的出现次数cnt[x]和位置列表pos[x]。
2. 若存在cnt[x] > 2，直接输出-1。
3. 初始化两个答案数组p和q，初始为0 00。
4. 处理出现2 22次的值：
   • 对于每个x xx，若cnt[x] == 2，设其两个位置为i和j。
   • 令p[i] = x，q[j] = x。
   • 记录自由槽：free_p.push_back(j)（表示p[j]待填），free_q.push_back(i)（表示q[i]待填）。
5. 处理出现1 11次的值：
   • 对于每个x xx，若cnt[x] == 1，设其唯一位置为i，令p[i] = q[i] = x。
6. 收集出现0 00次的值到zeros数组。
7. 将zeros中的值依次填入自由槽：
   • 第i d x idxidx个零数值y填入p[free_p[idx]] = y和q[free_q[idx]] = y。
8. 检查是否有任何位置仍为0 00（理论上不会发生），若有则输出-1；否则输出p和q。

4. 正确性说明

• 每个位置i ii都满足p i = a i p_i = a_ipi​=ai​或q i = a i q_i = a_iqi​=ai​：出现2 22次的值通过分别放在p pp和q qq的不同位置保证；出现1 11次的值直接两边都放；出现0 00次的值不影响条件，因为原位置的a i a_iai​已经由其他值满足。
• 排列性质：每个x ∈ [ 1 , n ] x\in[1,n]x∈[1,n]在p pp中恰好出现一次，在q qq中恰好出现一次。出现1 11次的值两个排列都有；出现2 22次的值分别放在一个排列的对应位置和另一个排列的自由槽；出现0 00次的值通过自由槽填入两个排列各一次。数量守恒保证刚好填满。

5. 复杂度分析

• 时间复杂度：O ( n ) O(n)O(n)，只需线性扫描数组、统计次数、填充答案。
• 空间复杂度：O ( n ) O(n)O(n)，存储位置列表、计数数组及答案数组。

总结

通过统计每个数值的出现次数，利用“出现两次的值制造自由槽，出现零次的值填充自由槽”的方式，在线性时间内构造出满足条件的两个排列。方法巧妙且高效，适用于10 5 10^5105规模的数据。

代码内容

#include<bits/stdc++.h>usingnamespacestd;#defineendl'\n'typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vvt;typedefpair<ll,ll>pll;constll N=1e3+10;constll INF=1e18;constll M=1e6+10;constll mod=1e9+7;intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);intn;cin>>n;vector<int>a(n);vector<vector<int>>pos(n+1);vector<int>cnt(n+1,0);for(inti=0;i<n;++i){cin>>a[i];cnt[a[i]]++;pos[a[i]].push_back(i);}for(intx=1;x<=n;++x){if(cnt[x]>2){cout<<"-1"<<endl;return0;}}vector<int>p(n,0),q(n,0);vector<int>free_p,free_q;// 储存自由槽位置（类型为p或q）vector<int>zeros;// 出现0次的数字// 处理出现两次的数字for(intx=1;x<=n;++x){if(cnt[x]==2){inti=pos[x][0],j=pos[x][1];// 将x放在p[i]和q[j]p[i]=x;q[j]=x;// 自由槽：q[i] 和 p[j]free_p.push_back(j);// p槽位置free_q.push_back(i);// q槽位置}}// 处理出现一次的数字for(intx=1;x<=n;++x){if(cnt[x]==1){inti=pos[x][0];p[i]=q[i]=x;}}// 收集零数for(intx=1;x<=n;++x){if(cnt[x]==0){zeros.push_back(x);}}// 将零数分配到自由槽中for(intidx=0;idx<(int)zeros.size();++idx){inty=zeros[idx];intpos_p=free_p[idx];intpos_q=free_q[idx];p[pos_p]=y;q[pos_q]=y;}// 检查是否所有位置都已填充for(inti=0;i<n;++i){if(p[i]==0||q[i]==0){cout<<"-1"<<endl;return0;}}// 输出p和qfor(inti=0;i<n;++i){cout<<p[i]<<(i==n-1?'\n':' ');}for(inti=0;i<n;++i){cout<<q[i]<<(i==n-1?'\n':' ');}return0;}