题解 | #苹果树#

思路：

题目的主要信息：

n棵苹果树上的果实存在数组a中
m天，每天要从每棵树上摘得苹果数存在数组b
对于某一天，对于每一棵树，若是苹果树上存留得苹果数大于等于 $b_i$ ，则摘取 $b_i$ 个，否则摘取剩余得全部
求每天各可以摘取共多少苹果

方法一：暴力法（超时）
具体做法：
我们可以遍历每一天，每天遍历数组a检查苹果树现有的苹果树，然后根据与b[i]的比较，摘取苹果并更新数组a。

class Solution {
public:
    vector<long> solve(vector<int>& a, vector<int>& b) {
        int n = a.size();
        int m = b.size();
        vector<long> res(m, 0);
        for(int i = 0; i < m; i++){ //遍历每天
            for(int j = 0; j < n; j++){ //遍历每棵树
                if(a[j] >= b[i]){ //若是够摘b[i]
                    a[j] -= b[i];
                    res[i] += b[i]; 
                }else{ //若是不够，则全部摘
                    res[i] += a[j];
                    a[j] = 0;
                }
            }

        }
        return res;
    }
};

复杂度分析：

时间复杂度： $O(mn)$ ，两层循环
空间复杂度： $O(1)$ ，常数级变量，其中res是返回函数必要空间，不属于额外空间

方法二：排序+前缀和
具体做法：
对于方法一，其实当数组a中的元素归零以后便不会再用了，但是我们还是对其遍历了，因此耗费了不少时间。我们可以考虑将数组a排列成一个递增序，前面的自然先归零。我们也不用去减到零，而是使用前缀和统计数组b前面几天共摘取了，前面自然会逐渐小于前缀和。我们用j表示上一次小于前缀和的下标，可以直接用 $(n - j) * b[i]$ 计算本次摘取数量，但是还需要循环减去本次（即j后面的）小于前缀和的苹果树，它们有多增加的数量。

class Solution {
public:
    vector<long> solve(vector<int>& a, vector<int>& b) {
        int n = a.size();
        int m = b.size();
        vector<long> res(m, 0);
        sort(a.begin(), a.end()); //排序
        long temp = 0; 
        for(int i = 0, j = 0; i < m; i++){
            temp += b[i]; //计算前缀和
            res[i] = long(n - j) * b[i]; //j前面的已经小于前缀和
            while(j < n && a[j] < temp) //减去j后面小于前缀和的
                res[i] -= temp - a[j++]; 
        }
        return res;
    }
};

复杂度分析：

时间复杂度： $O(nlog_2n+m)$ ，sort函数排序为 $O(nlog_2n)$ ，循环虽为两层，外循环为 $O(m)$ ，内循环总共只有 $n$ 次，故为 $O(m+n)$ ，舍去低次幂
空间复杂度： $O(1)$ ，常数级变量，其中res是返回函数必要空间，不属于额外空间

方法三：堆+前缀和
具体做法：
上述排序的方法我们也可以用堆来实现。首先所有数组a的元素进入小顶堆，进行堆排序，然后按照上述说法计算数组b的前缀和，本轮堆中元素都是大于上一轮的前缀和，我们直接堆大小乘上b[i]即可，只不过要再减去本轮中小于前缀和的那部分，然后将其弹出堆。
图片说明

class Solution {
public:
    vector<long> solve(vector<int>& a, vector<int>& b) {
        int n = a.size();
        int m = b.size();
        vector<long> res(m, 0);
        priority_queue<int, vector<int>, greater<int>> pq; //小顶堆
        for(int i = 0; i < n; i++) //数组a入堆
            pq.push(a[i]);
        long temp = 0;
        for(int i = 0; i < m; i++){
            temp += b[i]; //前缀和
            res[i] += pq.size() * b[i]; //堆中已经数量*b[i]
            while(!pq.empty() && pq.top() < temp){
                res[i] -= temp - pq.top(); //减去多计算的
                pq.pop(); //弹出小于前缀和的
            }
        }
        return res;
    }
};

复杂度分析：

时间复杂度： $O(nlog_2n+m)$ ，堆排序为 $O(nlog_2n)$ ，循环虽为两层，外循环为 $O(m)$ ，内循环总共只有 $n$ 次，故为 $O(m+n)$ ，舍去低次幂
空间复杂度： $O(n)$ ，堆空间最大长度为 $n$