忘记php网站后台密码,清河网站建设费用,长安英文网站建设,表格如何做网站文章目录 题目思路代码复杂度分析时间复杂度空间复杂度 结果总结 题目
题目链接#x1f517;
有一棵特殊的苹果树#xff0c;一连 n n n 天#xff0c;每天都可以长出若干个苹果。在第 i i i 天#xff0c;树上会长出 a p p l e s [ i ] apples[i] apples[i] 个苹果
有一棵特殊的苹果树一连 n n n 天每天都可以长出若干个苹果。在第 i i i 天树上会长出 a p p l e s [ i ] apples[i] apples[i] 个苹果这些苹果将会在 d a y s [ i ] days[i] days[i] 天后也就是说第 i d a y s [ i ] i days[i] idays[i] 天时腐烂变得无法食用。也可能有那么几天树上不会长出新的苹果此时用 a p p l e s [ i ] 0 apples[i] 0 apples[i]0 且 d a y s [ i ] 0 days[i] 0 days[i]0 表示。
你打算每天 最多 吃一个苹果来保证营养均衡。注意你可以在这 n n n 天之后继续吃苹果。
给你两个长度为 n n n 的整数数组 d a y s days days 和 a p p l e s apples apples 返回你可以吃掉的苹果的最大数目。
示例 1 输入apples [1,2,3,5,2], days [3,2,1,4,2] 输出7 示例 2 输入apples [3,0,0,5,0], days [3,0,0,4,0] 输出5 提示 1 ≤ a p p l e s . l e n g t h ≤ 5 ∗ 1 0 4 1 \leq apples.length \leq 5 * 10^4 1≤apples.length≤5∗104 0 ≤ a p p l e s [ i ] ≤ 5 ∗ 1 0 4 0 \leq apples[i] \leq 5 * 10^4 0≤apples[i]≤5∗104 1 ≤ d a y s [ i ] ≤ 5 ∗ 1 0 4 1 \leq days[i] \leq 5 * 10^4 1≤days[i]≤5∗104每天至少有一个苹果即 a p p l e s . l e n g t h d a y s . l e n g t h apples.length days.length apples.lengthdays.length。
思路
这个问题可以通过贪心算法来解决。我们可以维护一个优先队列最小堆存储未来几天内会坏掉的苹果。每天我们从队列中移除已经坏掉的苹果然后根据当前的苹果数量和剩余天数来决定每天可以吃多少苹果。
代码
class Solution {
public:int eatenApples(vectorint apples, vectorint days) {int d 0, ans 0;mapint, int dict; // 存储未来几天内会坏掉的苹果for (auto [n, t] : views::zip(apples, days)) {// 移除已经坏掉的苹果dict.erase(dict.begin(), dict.upper_bound(d));// 添加今天的苹果if (n)dict[d t] n;// 如果有苹果可以吃if (dict.size()) {ans;// 吃掉一个苹果if (!--dict.begin()-second)dict.erase(dict.begin());}d;}// 继续吃剩下的苹果while (dict.size()) {dict.erase(dict.begin(), dict.upper_bound(d));if (dict.empty())return ans;auto [t, n] *dict.begin();dict.erase(dict.begin());int tmp min(t - d, n);d tmp;ans tmp;}return ans;}
};复杂度分析
时间复杂度 O ( n l o g n ) O(nlogn) O(nlogn)其中 n n n 是苹果的天数。主要时间消耗在对 map 的操作每次插入和删除操作的时间复杂度为 O ( l o g n ) O(logn) O(logn)。
空间复杂度 O ( n ) O(n) O(n)
结果 总结
本题是一个贪心算法的问题关键在于理解如何维护一个存储未来几天内会坏掉的苹果的数据结构并据此计算每天可以吃多少苹果。
