1、植树

题目描述

小多想在美化一下自己的庄园。他的庄园毗邻一条小河，他希望在河边种一排树，共 M 棵。小多采购了 N 个品种的树，每个品种的数量是 Ai (树的总数量恰好为 M)。但是他希望任意两棵相邻的树不是同一品种的。小多请你帮忙设计一种满足要求的种树方案。

代码

import numpy as np 
import sys   
sys.setrecursionlimit(100000)  #!!!设置递归深度，递归算法最好每次都加这样的设置，不然牛客上会报错
def dfs(trees, result, remain_num, prev):
    for i in range(len(trees)):

        if 2*trees[i] > remain_num+1: #解方程得出
            return False

        if trees[i] > 0 and i != prev: 
            result.append(i+1)
            trees[i] -= 1
            remain_num -= 1

            if dfs(trees, result, remain_num, i): 
                return True
            else:
                del result[-1]
                trees[i] += 1
                remain_num += 1
    
    return True

tree_kinds=int(input())
trees=[int(num) for num in input().split(" ")]
result=[]
m=sum(trees)
if(dfs(trees,result,m,-1)):
  for ele in result:
    print(ele,end=" ")
else:
  print("-")

方程

x为当前树苗的的剩余数目，n为其他树苗的剩余数目，m为还剩树苗和。这些变量之间满足如下方程:


解得：