壁垒

思路

这是一道构造题。

首先，计算出数的种类数。如果种类数是奇数，就无法构造，反之可以。

证明：种类数是奇数时，前 𝑛 n 个数的种类数就一定是奇数。当种类数是偶数时，设数列中数的种类数为 𝑘 k，则构造数列，使得构造的数列前 𝑘 k 项均不相同，剩下的位置把剩余的数输出即可。

Code

#include<bits/stdc++.h>
using namespace std;
int n,a[100005],sum,vis[100005];
int main(){
	cin>>n; for(int i=1;i<=n;i++) cin>>a[i],vis[a[i]]++;
	sort(a+1,a+n+1); sum=1;
	for(int i=2;i<=n;i++) if(a[i]!=a[i-1]) sum++;
	if(sum%2==1) {cout<<"-1"; return 0;}
	cout<<a[1]<<" ";
	for(int i=2;i<=n;i++) if(a[i]!=a[i-1]) cout<<a[i]<<" ";
	for(int i=1;i<=n;i++) while(vis[i]>1) vis[i]--,cout<<i<<" ";
	return 0;
}