题解

解法一

直接暴力模拟;
枚举每一天，然后枚举每棵树，更新树上的苹果数量，计算答案。
时间复杂度为

解法二

前缀和+堆

假设一棵树 在第X天被摘完 我们可以发现 (1--X-1)天的采摘量是和计划是一样的
所以我们可以利用这一个特点 对于每一天去维护有多少棵树的采摘量和计划数相同

我们先将B数组做一个前缀和sum，sum[i]即代表前i天按计划每棵树要被摘多少个苹果
然后将所有a[i]放到一个小根堆里面
我们依次枚举每一天，怎么计算答案呢？
如果当前堆顶元素<sum[i] 意味这它将在第i天被摘完，我们即可将它在小根堆中删除。
然后这一天的答案即是 当前小根堆里元素个数*b[i]+第i天被摘完的苹果树的当天采摘量之和
时间复杂度

#include<bits/stdc++.h>
using namespace std;
class Solution {
public:
    /**
     *
     * @param a int整型vector
     * @param b int整型vector
     * @return long长整型vector
     */
    long long sum[100005];
    priority_queue<long long ,vector<long long >,greater<long long > >q;

    vector<long> solve(vector<int>& a, vector<int>& b) {
        // write code here
        vector<long>ans;
        int m=b.size();
        int n=a.size();
        for (int i=0; i<m; i++)
        {
            sum[i]=b[i];
            if (i>0) sum[i]+=sum[i-1];
        }

        for (int i=0; i<n; i++)
        {
            q.push(a[i]);
        }
        for (int i=0; i<m; i++)
        {
            long long tmp=0;
            while (!q.empty() && q.top()<=sum[i])
            {
                long long x;
                if (i>0) x=q.top()-sum[i-1];
                else x=q.top();
                tmp+=x;
                q.pop();
            }
            tmp+=1ll*b[i]*q.size();
            ans.push_back(tmp);
        }
        return ans;
    }
};