【在线编程产品介绍】

阿里云开发者社区在线编程：

免费刷题大神器，助你拿到好offer

周赛月赛不停歇，做题还能领奖品

大赛笔试全真题，常做常新有惊喜

点击链接开始产品体验：https://developer.aliyun.com/coding

本文为大家介绍的是“101.采摘圣诞果”的解法探究。先来看一下题目内容：

题目详情

等级：中等
知识点：贪心
查看题目：采摘圣诞果

圣诞节马上就要来了，果园里的 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
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)

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

在线编程周赛、月赛火热进行中，更有限时答题活动，社区定制卫衣、双肩背包等你来拿~每天都有好礼相送~点击了解周赛详情：在线编程3月份比赛正式开启！机械键盘等你拿！