首页 > 试题广场 >

种树

[编程题]种树
  • 热度指数：7824 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解 
小多想在美化一下自己的庄园。他的庄园毗邻一条小河，他希望在河边种一排树，共 M 棵。小多采购了 N 个品种的树，每个品种的数量是 Ai (树的总数量恰好为 M)。但是他希望任意两棵相邻的树不是同一品种的。小多请你帮忙设计一种满足要求的种树方案。

输入描述:
第一行包含一个正整数 N，表示树的品种数量。
第二行包含 N 个正整数，第 i (1 <= i <= N) 个数表示第 i 个品种的树的数量。
数据范围：
1 <= N <= 1000
1 <= M <= 2000


输出描述:
输出一行，包含 M 个正整数，分别表示第 i 棵树的品种编号 (品种编号从1到 N)。若存在多种可行方案，则输出字典序最小的方案。若不存在满足条件的方案，则输出"-"。
示例1

输入

3
4 2 1

输出

1 2 1 2 1 3 1
算法知识视频讲解
添加回答
Python
牛客606857817号头像 牛客606857817号
为啥同样的算法C++可以通过，python通不过
N=int(input())
a=[int(i) for i in input().split()]
m=sum(a)
if max(a)-(sum(a)-max(a))>2:
    print('-')
else:
 def add(a,left,out):
    if len(out)<m:
        for i in range(1,N+1):
           if i!=left and a[i-1]>0:               
             a[i-1]=a[i-1]-1
             if max(a)-(sum(a)-max(a))<2:
               out.append(i)   
               add(a,i,out)  
             else:
               a[i-1]=a[i-1]+1
               dex=a.index(max(a))
               a[dex]=a[dex]-1
               out.append(dex+1)
               add(a,dex+1,out)              

 out=[]
 add(a,-1,out)
 o=[]       
 for i in out:
  o.append(str(i))        
 print(' '.join(o)) 


编辑于 2020-04-18 11:20:33 回复(1)
Python
Bhigher头像 Bhigher
N = int(input())
nums = list(map(int,input().split()))
tree = [i for i in range(1,sum(nums)+1)]
nums[0] -= 1
for i in range(1,sum(nums)+1):
    tree[i] = 1
    while tree[i]==tree[i-1] or nums[tree[i]-1]==0:
        tree[i]= tree[i]+1
        if tree[i] > N:
            print('-1')
    nums[tree[i]-1] -= 1
tree1=''
for i in range(len(tree)):
    tree1 += str(tree[i])
    if i!= len(tree)-1:
        tree1 += ' '
print(tree1)

渣渣通过率35%
发表于 2019-07-28 00:02:49 回复(2)
提交观点

问题信息

C++工程师 golang工程师 iOS工程师 数组 安卓工程师 运维工程师 前端工程师 算法工程师 测试工程师 PHP工程师 递归 贪心 2019 拼多多集团-PDD Java工程师
上传者：小小
难度：
3条回答 18220浏览

热门推荐

通过挑战的用户

查看代码

相关试题

种树

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号