题意分析

给出一个初始的序列，表示一开始的苹果树上的苹果的数量，然后，给出每一天需要从每棵树上摘的苹果的数量。如果这棵树上的苹果的数量不够了，那么就全部摘除。

思路分析

思路一堆优化

首先，我们发现，对于苹果树上的苹果的数量这个序列，位置的先后关系是可以调换的，这不会影响最后的结果。然后，由于每一天都需要从所有的苹果树上面采摘一些苹果，肯定是苹果树上果子少的先被采摘完。所以我们可以用一个小根堆来维护当前序列里面最小的苹果树的数量，对于第i天的需要的苹果的数量，我们先找到所有的不够这天摘的苹果的树的棵数。然后剩下的苹果树就一定可以摘满这一天的苹果了。所以我们每次取出堆顶的元素，直到剩下的可以满足这一天的采摘量。然后，对于不能满足当天的采摘量的苹果树，我们先利用一个前缀变量计算从最开始到这一天所需要的总的苹果的数量，然后减去这棵苹果树上的苹果的数量，就是还差的苹果的数量，最后我们用这一天需要采摘的苹果的数量减去前面所求的数就是这一天在这棵苹果树上的采摘量了。
这里我们为了方便，利用了C++的STL容器，就是优先队列小根堆优化。
代码如下
- 利用堆进行优化，每次堆调整的时间复杂度为 $O (l o g n)$ ，最多会调整n次，所以总的时间复杂度为 $O (n l o g n)$
- 求解过程中只用了少数几个变量进行处理，空间复杂度为 $O (1)$

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param a int整型vector 
     * @param b int整型vector 
     * @return long长整型vector
     */
    priority_queue<int,vector<int>,greater<int> > q;
    vector<long> solve(vector<int>& a, vector<int>& b) {
        // write code here
        for(auto x:a){
            q.push(x);
        }
        
        
        vector<long> ans;
        int num=a.size(); // 用来记录当前可以正常采摘的苹果树的数量
        int sum=0;  // 用来记录之前所摘过的所有的苹果数量的和
        for(auto x:b){
            long need=sum+x;  // 记录这棵树初始的时候需要多少苹果才能保证当前可以正常采摘
            long total=0;
            while(!q.empty()&&q.top()<need){
                total+=(x-(need-q.top())); // 不足的时候，我们用当前所需要采摘的果实的数量减去还差的数量就是实际采摘的数量
                q.pop();
                num--;  // 一棵苹果树被摘完了
            }
            // 先特判是否还有没有摘完的苹果树
            if(num!=0){
                total+=(long)num*x;
            }
            ans.push_back(total);
            sum+=x;
        }
        
        
        return ans;
    }
};

思路二排序

第二种思路的来源是第一种思路的简化，我们发现，由于我们每天都需要从每棵苹果树采摘相同的数量的苹果，所以这些苹果树上的苹果的数量的相对大小是不变的，最多就是大家的数量都为0了。在上一种思路的基础上，我们发现，我们可以先对苹果树的苹果数量这个序列进行排序，排好序后，对于每一天需要采摘的苹果的数量，我们需要做的是利用计算当天哪些苹果树不够采摘了，然后剩下的就是能满足当天的了。累加到这一天的答案即可。这里同样需要用一个前缀和变量来存储之前的所有的天数的采摘总量的前缀和。
如下图

alt

代码如下
- 利用了sort进行排序，时间复杂度为 $O (n l o g n)$
- 在求解过程中只用了少数的几个变量，空间复杂度为 $O (1)$

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param a int整型vector 
     * @param b int整型vector 
     * @return long长整型vector
     */
    vector<long> solve(vector<int>& a, vector<int>& b) {
        // write code here
        sort(a.begin(),a.end());
        
        
        int n=a.size();
        int m=b.size();
        vector<long> ans;
        long pre=0; // 前缀和，记录到达当前天所需要的苹果的数量
        for(int i=0,j=0;i<m;i++){
            pre+=b[i];  // 记录[0,i]的前缀和
            long sum=0;
            // 先看一下不足当前所需要的所有苹果数量的苹果树
            while(j<n&&a[j]<pre){
                sum=sum+(b[i]-(pre-a[j]));
                j++;
            }
            // 剩下的(n-j)就都是满足题目条件的苹果树了，这些苹果树一定能正常摘b[i]个
            sum=sum+(n-j)*b[i];
            ans.push_back(sum);
        }
        
        
        return ans;
    }
};

NC582 题解 | #苹果树#

题意分析

思路分析

思路一 堆优化

思路二 排序

思路一堆优化

思路二排序