网站的规划与创建,sogo提交网站入口,东莞seo建站投放,wordpress怎么集成码支付宝文章目录1. 题目2. 解题1. 题目
有一棵特殊的苹果树#xff0c;一连 n 天#xff0c;每天都可以长出若干个苹果。 在第 i 天#xff0c;树上会长出 apples[i] 个苹果#xff0c;这些苹果将会在 days[i] 天后#xff08;也就是说#xff0c;第 i days[i] 天时#xff0…
文章目录1. 题目2. 解题1. 题目
有一棵特殊的苹果树一连 n 天每天都可以长出若干个苹果。 在第 i 天树上会长出 apples[i] 个苹果这些苹果将会在 days[i] 天后也就是说第 i days[i] 天时腐烂变得无法食用。 也可能有那么几天树上不会长出新的苹果此时用 apples[i] 0 且 days[i] 0 表示。
你打算每天 最多 吃一个苹果来保证营养均衡。注意你可以在这 n 天之后继续吃苹果。
给你两个长度为 n 的整数数组 days 和 apples 返回你可以吃掉的苹果的最大数目。
示例 1
输入apples [1,2,3,5,2], days [3,2,1,4,2]
输出7
解释你可以吃掉 7 个苹果
- 第一天你吃掉第一天长出来的苹果。
- 第二天你吃掉一个第二天长出来的苹果。
- 第三天你吃掉一个第二天长出来的苹果。过了这一天第三天长出来的苹果就已经腐烂了。
- 第四天到第七天你吃的都是第四天长出来的苹果。示例 2
输入apples [3,0,0,0,0,2], days [3,0,0,0,0,2]
输出5
解释你可以吃掉 5 个苹果
- 第一天到第三天你吃的都是第一天长出来的苹果。
- 第四天和第五天不吃苹果。
- 第六天和第七天你吃的都是第六天长出来的苹果。提示
apples.length n
days.length n
1 n 2 * 10^4
0 apples[i], days[i] 2 * 10^4
只有在 apples[i] 0 时days[i] 0 才成立来源力扣LeetCode 链接https://leetcode-cn.com/problems/maximum-number-of-eaten-apples 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
参考大佬https://leetcode-cn.com/problems/maximum-number-of-eaten-apples/solution/c-you-xian-dui-lie-mo-ni-by-fdl-kdvx/
优先队列贪心先过期的先吃
typedef pairint,int pii;
struct cmp
{bool operator()(pii a, pii b) const{return a.first b.first;//小的先过期的优先吃}
};
class Solution {
public:int eatenApples(vectorint apples, vectorint days) {priority_queuepii,vectorpii, cmp q;//pair 过期时间剩余的果子数量int eat 0, n apples.size();for(int i 0; i n || !q.empty(); i) {while(!q.empty() q.top().firsti)//苹果过期了删除q.pop();if(i n apples[i] 0)//当前的苹果加入优先队列q.push({idays[i], apples[i]});if(!q.empty()){pii t q.top();q.pop();eat;//吃一个if(--t.second 0)//这一堆还没吃完q.push(t);}}return eat;}
};892 ms 46.2 MB C 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
