题解: S001A 壁垒

传送门

思路&解题方法

首先发现如果种类数本身为奇数，则一定无解（整个数列也算一个前缀）

发现可以对构造出来的数列进行分析。前缀两个两个地增加，不难发现，每次要么增加 $0$ 种数字，要么增加 $2$ 种数字。

构造时，可以先将偶数种数字依次用一遍（每次增加 $2$ 种），然后就随便放了，因为剩下的数字前面都出现过，每次只有可能增加 $0$ 种数字。

所以，在种类数为偶数时，肯定有解。

复杂度

时间复杂度:

$O(n)$

空间复杂度:

$O(n)$

Code

#include<bits/stdc++.h>
using namespace std;
const int N=100005;
int times[N];
vector<int>ans;

int main() {
    int n, m=0;
    scanf("%d", &n);
    for(int i=0; i<n; i++) {
        int x;
        scanf("%d", &x);
        ++times[x];
        if(times[x]==1)
            ++m; // 用m记录种类数
    }
    if(m%2)
        return printf("-1\n")&0; // 无解的情况
    for(int i=1; i<=n; i++) {
        if(times[i]==0)
            continue;
        printf("%d ", i);
        --times[i];
    } // 第一遍，每个种类都消耗一遍，增加2种数字
    for(int i=1; i<=n; i++) {
        while(times[i]) {
            --times[i];
            printf("%d ", i);
        }
    } // 第二遍，每次总是增加0种数字
    puts("");
    return 0;
}