题解 | #种树#_牛客博客

思路

由于同种类树不能相邻，因此我们若间隔种植同种树木，若能成功种植，其长度不会超过 $M$ 。设第 $i$ 种树木有 $A_i$ 棵，根据 $M$ 的奇偶性，我们可以考虑两种极端情况：

若 $M$ 为奇数，则最多能种植的同种树木数量满足 $2A_i=M+1$ ，如下图所示：
若 $M$ 为偶数，则最多能种植的同种树木数量满足 $2A_i=M$ ，如下图所示：

显然，若树木多于上述情况，则将不存在方案。故若 $2A_i>M+1$ ，那么可以直接判断方案不存在。那么当对任意 $i$ ， $2A_i\le M+1$ 时，一定存在不相邻种植的方案吗？

答案是一定的！我们可以尝试构造出这样的解：我们按树木编号顺序从头至尾间隔种植，到达尾部后重新从第二个槽位开始间隔种植。

下图我们依次按照蓝色、橙色、红色、黄色间隔种植，且 $M$ 为偶数的情况。 alt 如果此时存在相邻的同种树木，那么一定一棵来自于第一趟种植，一棵来自第二趟种植，如下图红色树木。 alt 此时，红色树木数量为 $2A_{red}\ge M$ ，而在 $M$ 为偶数时，能种植的树木数量满足 $2A_{red}\le M$ ，因此这种情况只有两个同种树木相邻。此时我们变换策略，将所有红色树木种在偶数位或奇数位，那么其余位任意种植树木均满足条件。

当 $M$ 为基数时，若发生相邻树木为同种的情况： alt 则必然有 $2A_{red}=M+1$ ，此时所有红色树木应全部种植在奇数位，其他所有树木任意种植均满足条件。

综上所述，若所有树木均满足 $2A_i\le M+1$ ，则必然存在解。并且若存在 $2A_i=M+1$ ，则第一个槽位只能种植该种树木，否则第一个槽位可以种植任意树木。

因此我们可以得到一个贪心方案：若有解，并且不存在 $2A_i=M+1$ ，则我们置此槽位为序号最小的剩余树木，并在之后规模为 $M-1$ 的数组寻找第一个槽位与该槽位不同的解；若存在 $2A_i=M+1$ ，则直接置为 $i$ ，并在之后规模为 $M-1$ 的数组寻找第一个槽位与该槽位不同的解。若无解，直接输出即可。

代码

#include <iostream>
using namespace std;
int N, M = 0;
int A[1001]{};
int res[2001]{};

int main() {
    ios_base::sync_with_stdio(false);
    cin>>N;
    for(int i=1;i<=N;++i) { cin>>A[i]; M+=A[i]; }
    for(int i=1;i<=N;++i) if((M+1)<2*A[i]) {
        cout<<"-";
        return 0;
    }
    for(int j=1;j<=M;++j){
        int len = M+1-j;
        int i=0;
        if(len & 0x1) {
            for(i=1;i<=N;++i) if(2*A[i]==len+1) {
                res[j]=i;
                --A[i];
                break;
            } 
        } 
        if(i==N+1 || !(len & 0x1)){
            for(i=1;i<=N;++i) if(A[i]>0 && i!=res[j-1]) {
                res[j]=i;
                --A[i];
                break;
            }
        }
    }
    for(int j=1;j<=M;++j) cout<<res[j]<<" ";
    return 0;
}

时间复杂度： $O(MN)$
空间复杂度： $O(M+N)$