题解：P10672 【MX-S1-T1】壁垒

wimg6_ · 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;
}

更新日志

修改了一处笔误。