首页 > 试题广场 >

种树

[编程题]种树
  • 热度指数：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
算法知识视频讲解
开通博客
头像 牛客题解官
发表于 2020-06-05 18:46:14
精华题解 题解： 题目难度：三星 考察点： 深度优先搜索，回溯，剪枝 易错点： 这个题目对于同学们来说做法非常直接，就是递归+回溯，也很容易想。但是因为物品的数量达到了，如果用简单的不进行剪枝的话，是无法跑过所有数据的，因此需要做一些剪枝。 题解：深度优先搜索+剪枝 这个题目的做法很显然，就是使用递归+回溯， 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 白色高跟鞋
发表于 2020-04-26 02:45:25
思路：dfs+剪枝。(见代码)要注意的是同样的思路python由于递归上限的问题过不了，因此需要手动设置sys.setrecursionlimit()。 import sys # python 默认递归深度不超过1000，做dfs会比C吃亏 sys.setrecursionlimit(1000000 展开全文
去ta的博客 赞 (4) 回复(0) 收起
头像 降龙尊者
发表于 2020-12-31 09:56:55
dfs+剪枝注意剪枝条件:如果还剩下2k+1个坑位, 最多有k+1个树属于同一个种类如果还剩下2k个坑位, 最多有k个树属于同一个种类 所以剪枝条件为: 2*树i的数量 > (剩余坑位+1) package t2; import java.util.ArrayList; import jav 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 Fcber
发表于 2024-10-26 18:50:50
思路 由于同种类树不能相邻，因此我们若间隔种植同种树木，若能成功种植，其长度不会超过 。设第 种树木有 棵，根据 的奇偶性，我们可以考虑两种极端情况： 若 为奇数，则最多能种植的同种树木数量满足 ，如下图所示： 若 为偶数，则最多能种植的同种树木数量满足 ，如下图所示： 显然，若树 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

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

热门推荐

通过挑战的用户

查看代码

相关试题

种树

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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