前两天在codeforce上见到一个挺有意思的题，现在尝试写个题解。

原题链接：Constructive Problem

Adam has an array a consisting of n integers a0,a1,…,an-1. We call this array beautiful if the number of occurrences of i is ai for i ∈ [0,n−1].

For example:

  • [1,2,1,0] is beautiful. In this array, 0 appears 1 time, 1 appears 2 times, 2 appears 1 time, and 3 appears 0 times, and a0=1,a1=2,a2=1,a3=0.
  • [0,1] is not beautiful. Because a0=0 but in fact 0 appears 1 time.

Find a beautiful array of length n. If there are multiple answers, output any. If there is no beautiful array of length n, output −1.

Input
The input contains an integer n (1≤n≤106) — the length of the beautiful array.
Output
Output a beautiful array of length n. If there are multiple answers, output any. If there is no beautiful array of length n, output −1.

Examples
input
4
output
1 2 1 0
input
2
output
-1
Note
In Example 1, [1,2,1,0] or [2,0,2,0] are both beautiful array of length 44, and you can output any of them.

题目描述非常浅显，目的在于生成给定长度的“完美”数列。
最后还来一句”If there are multiple answers, output any.”答案不唯一，这也意味着得找到一般性的方法。

先来看第一个例子，最后一位0表示数列当中没有3，需要想到最后一位只能是零，还有就是第一位不能是零（想想不符合会出啥情况），然后我想要一个很长的，可是因为它的规则，很容易“牵一发而动全身”，那么能不能尽量少用0以外的数字来填充？

答案是肯定的，你会发现1，2，1正好对应0，1，2的数目，如果往后面加0的话，之后第一步只需要改变第一位对吧？(零的数目X)
然后好办了，改变了第一位，你需要在后面的0中找到数列第一位数字所对应的0，把它改成1，巧合的是，前面的X，2，1不需要再改变了。

还没完，很明显长度3及以下的这种数列不可能找到，会自相矛盾，前几个情况也比较特殊，不能用上面的方法，因为要从后面改变的0根本不在后面，而n=6时，无论如何对第一个数取值后面都会矛盾，7以后就没问题了。

代码非常简短

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n=0;
    cin>>n;
    if(n<=3||n==6) cout<<"-1";
    else if(n==4) cout<<"1 2 1 0";
    else if(n==5) cout<<"2 1 2 0 0";
    else{
        cout<<n-4<<" 2 1 ";
        for(int i=0;i<n-7;i++) cout<<"0 ";
        cout<<"1 "<<"0 0 0";
    }
    return 0;
}