遇到一个贪心算法问题，求解答。
圣诞节马上就要来了，果园里的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）。输出一个数字，表示最多可以收获的圣诞果数。
写回答
-
定义数组a[i]表示第i天可以采摘的刚刚结出来的果子，数组b[i]表示第i天可以采摘的已经过了一天的果子。根据输入先初始化 a[]。假设我们当前处于第i天，那么显然我们应该采摘b[i]中的果实，然后再采摘a[i]中的果实，因为如果不采摘b[i]中的果实，则它们会在下一天被偷吃。在更新之后 a[i] 中剩余的果实会在下一天变成b[i]中的果实。 因此：输入：3 3 [[1,3],[2,5],[3,4]] 输出：12 注：你可以在第一天在第一棵树上摘三个，第二天在第二棵树上摘三个，第三天在第二棵树上摘两个，然后再在第三颗树上摘一个，第四天在第三棵树上摘三个。
2021-12-23 18:28:45赞同 展开评论 打赏
版权声明：本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
