← 返回目录

算法笔试模拟题精解之“采摘圣诞果”

第 14 / 74 卷日期：

算法笔试模拟题精解之“采摘圣诞果”

贡献者 | 猿圈

简介：我们定义数组 a[i] 表示第 i 天可以采摘的刚刚结出来的果子，数组 b[i] 表

示第 i 天可以采摘的已经过了一天的果子。根据输入先初始化 a[]。

题目描述

等级：中等

知识点：贪心

查看题目：采摘圣诞果

圣诞节马上就要来了，果园里的 n 棵圣诞树马上就要结果子了，每棵圣诞树会在

第 a[i] 天结出 b[i] 个果实。果园里有许多圣诞小精灵，它们非常喜欢吃圣诞果，如果

在结果后两天内也就是第 a[i] 天和第 a[i]+1 天，没有将果实采摘下来，那么将会被小

精灵们偷吃掉。

你，作为圣诞树的看守者，必须采摘尽可能多的圣诞果，但是你每天最多只能采

摘 v 个圣诞果，当然，可以是不同的果树上的。现在你需要判断自己最多可以收获多

少圣诞果。

输入圣诞树棵树 n、每天最多采摘的圣诞果数量 v 和一个数组 m，其中 m[i]=[a[i],

b[i]] 表示每棵圣诞树第 a[i] 天结出 b[i] 个果实（1 <= n，a[i]，b[i] <= 3000）。

输出一个数字，表示最多可以收获的圣诞果数。

示例 1

输入：

3

[[1,3],[2,5],[3,4]]

输出：

12

注意

你可以在第一天在第一棵树上摘三个，第二天在第二棵树上摘三个，第三天在第

二棵树上摘两个，然后再在第三颗树上摘一个，第四天在第三棵树上摘三个。

解题思路描述

我们定义数组 a[i] 表示第 i 天可以采摘的刚刚结出来的果子，数组 b[i] 表示第 i

天可以采摘的已经过了一天的果子。根据输入先初始化 a[]。

假设我们当前处于第 i 天，那么显然我们应该采摘 b[i] 中的果实，然后再采摘

a[i] 中的果实，因为如果不采摘 b[i] 中的果实，则它们会在下一天被偷吃。在更新之

后 a[i] 中剩余的果实会在下一天变成 b[i] 中的果实。

时间复杂度：O(3000)

空间复杂度：O(3000)

看完之后是不是有了答题思路了呢，快来练练手吧：采摘圣诞果

全站分卷索引 · 74 卷
  1. 1一、算法思想
  2. 2算法笔试模拟题精解之“打怪兽”
  3. 31.2 贪心
  4. 4算法笔试模拟题精解之“最强的团队”
  5. 5算法笔试模拟题精解之“Tom 爱吃巧克力”
  6. 6算法笔试模拟题精解之“吃奶酪”
  7. 7算法笔试模拟题精解之“一的个数”
  8. 8算法笔试模拟题精解之“Bob 的花束”
  9. 9算法笔试模拟题精解之“钱庄”
  10. 10算法笔试模拟题精解之“移动射击”
  11. 11算法笔试模拟题精解之“相似数组”
  12. 12算法笔试模拟题精解之“过吊桥”
  13. 13算法笔试模拟题精解之“完美排列”
  14. 14算法笔试模拟题精解之“采摘圣诞果”
  15. 15算法比赛模拟题精解之“Tairitsu and Dynamic Objects”
  16. 16算法笔试模拟题精解之“Codancer 的炸弹引爆”
  17. 17算法笔试模拟题精解之“学习小组”
  18. 18算法笔试模拟题精解之“恢复字符串”
  19. 191.3 DP/ 动态规划
  20. 20算法笔试模拟题精解之“寻找等比数列”
  21. 21算法笔试模拟题精解之“字符配对”
  22. 22算法笔试模拟题精解之“数组染色”
  23. 23算法笔试模拟题精解之“连绵的群山”
  24. 24算法笔试模拟题精解之“难住Tom 的问题”
  25. 25算法笔试模拟题精解之“变化的字符”
  26. 26算法笔试模拟题精解之“跳房子”
  27. 27算法笔试模拟题精解之“寒假活动”
  28. 28算法笔试模拟题精解之“最短路”
  29. 29算法笔试模拟题精解之“codancer 上楼”
  30. 30算法笔试模拟题精解之“木棒拼接”
  31. 31算法笔试模拟题精解之“Codancer 的数组封印”
  32. 32算法笔试模拟题精解之“Jerry 的异或运算”
  33. 33算法笔试模拟题精解之“小明的数学作业”
  34. 34算法笔试模拟题精解之“奇偶数列”
  35. 351.4 剪枝
  36. 361.5 尺取法
  37. 37算法笔试模拟题精解之“调整数组”
  38. 38算法笔试模拟题精解之“最优分组”
  39. 39算法笔试模拟题精解之“破译密码”
  40. 40二、数据结构
  41. 412.2 搜索
  42. 42算法笔试模拟题精解之“能量半径”
  43. 43算法笔试模拟题精解之“苹果收获程序”
  44. 44算法笔试模拟题精解之“恐怖的辐射”
  45. 45算法笔试模拟题精解之“树的拆分”
  46. 46算法笔试模拟题精解之“Password”
  47. 47算法笔试模拟题精解之“神奇数字在哪里”
  48. 48算法笔试模拟题精解之“神奇的棋子”
  49. 492.3 树
  50. 50算法笔试模拟题精解之“Codancer 的旅行”
  51. 51算法笔试模拟题精解之“Codancer 的求和”
  52. 52算法笔试模拟题精解之“找出二叉搜索树的第2 大的数”
  53. 532.4 线型
  54. 54算法笔试模拟题精解之“最活跃的数”
  55. 55算法笔试模拟题精解之“非递减序列”
  56. 56算法笔试模拟题精解之“Tom 跳方格”
  57. 57算法笔试模拟题精解之“复杂的字符串”
  58. 58算法笔试模拟题精解之“神秘消失”
  59. 59三、计算
  60. 60算法笔试模拟题精解之“简单题？
  61. 61算法笔试模拟题精解之“朋友一生一起走”
  62. 62算法笔试模拟题精解之“正三角塔”
  63. 63算法笔试模拟题精解之“组队难题”
  64. 64算法笔试模拟题精解之“2n 合体”
  65. 65算法笔试模拟题精解之“平行线”
  66. 66算法笔试模拟题精解之“叠叠高”
  67. 67算法笔试模拟题精解之“公平”
  68. 68算法笔试模拟题精解之“Tom 的手工课”
  69. 69算法笔试模拟题精解之“填数问题”
  70. 70算法笔试模拟题精解之“Jerry 的考验”
  71. 71算法笔试模拟题精解之“超车”
  72. 72算法笔试模拟题精解之“坏掉的时钟”
  73. 73算法笔试模拟题精解之“期末考试”
  74. 74算法笔试模拟题精解之“滑雪比赛”