自动搬运

查看原文

来自洛谷，原作者为

	wimg6_ 1+1=？

搬运于2025-08-24 23:00:07，当前版本为作者最后更新于2024-06-29 19:44:00，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

注意到，我们可以先统计 $a$ 数组中出现过多少个不同的数字，记为 $s$。

若 $s$ 为奇数，则无论怎么构造，对于 $a$ 的前缀 $a_1\sim a_n$，其一定不符合题意，故输出 $-1$。

若 $s$ 为偶数，则我们可以先取每个出现过的数字各一遍，然后任意取即可。为什么？因为对于前缀 $a_1\sim a_i(2\leq i\leq s,i=2k,k\in \mathbb{Z}_+)$，其出现的数字种类数均为 $i$，而 $i$ 又是偶数，所以成立；而对于前缀 $a_1\sim a_i(s<i\leq n,i=2k,k\in \mathbb{Z}_+)$，其出现的数字种类数均为 $s$，而 $s$ 又是偶数，所以也成立。

#include<bits/stdc++.h>
using namespace std;
int n,flag,a[100010],f[100010];
int read(){
    int x=0,p=1;char ac=getchar();
    while(ac!='-' && (ac<'0' || ac>'9')) ac=getchar();
    if(ac=='-') p=-1;
    while(ac>='0' && ac<='9') x=x*10+ac-'0',ac=getchar();
    return x*p;
}
int main(){
    n=read();
    for(int i=1;i<=n;i++){
        a[i]=read(),f[a[i]]++;
        if(f[a[i]]!=1) flag++;
    }
    if(flag%2) return !printf("-1");
    for(int i=1;i<=100000;i++)
        if(f[i]) printf("%d ",i),f[i]--;
    for(int i=1;i<=100000;i++)
        while(f[i])
            printf("%d ",i),f[i]--;
    return 0;
}

更新日志

修改了一处笔误。