题解 | #苹果树#

题目描述：
有n棵果树，第i棵果树的果子数量为 $a_{i}$ ,摘m天的果子，每天每棵树摘 $b_{i}$ 个果子，返回每天摘的果子数量总和数组
方法一：暴力解法
枚举每天对每棵树摘的果子数量 $b_{i}$ 和所有的果树 $a_{i}$ ,如果第i棵果树的果子数量 $a_{i}$ 大于要摘的果子数量，第i天摘的果子数量增加 $b_{i}$ ， $a_{i}$ 相应减少；否则，第i天摘的果子数量增加 $a_{i}$ ， $a_{i}$ 相应减少

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param a int整型一维数组 
     * @param b int整型一维数组 
     * @return long长整型一维数组
     */
    public long[] solve (int[] a, int[] b) {
        // write code here
        long[]res=new long[b.length];
        for(int i=0;i<b.length;i++){
            for(int j=0;j<a.length;j++){
                if(a[j]>b[i]){res[i]+=b[i];a[j]-=b[i];}
                else {res[i]+=a[j];a[j]-=a[j];}
            }
        }
        return res;
    }
}

复杂度：
时间复杂度：暴力解法的时间复杂度高达 $O(mn)$ ,会超时
空间复杂度:辅助数组res大小不超过n, $O(n)$
方法二：最小堆
果子数量少的树会先耗尽，因此我们先摘果子数量少的树，将果树存储在一个最小堆里面，在m天中，我们每次都先摘堆顶果树的果子（即现存果树中果子数量最少的果树），假设第i天现存果树都能摘完，即第i天摘到的果子数为 $q.size()*b[i]$ ,但是显然，果子数量少的树会先耗尽，因此当所摘果子的数量已经超过堆顶果树数量时，减去多摘的果子，堆顶果树也会耗尽出队

图片说明

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param a int整型一维数组 
     * @param b int整型一维数组 
     * @return long长整型一维数组
     */
    public long[] solve (int[] a, int[] b) {
        // write code here
        int m=b.length;
        int n=a.length;
        long[]res=new long[m];
        PriorityQueue<Integer>q=new PriorityQueue<>();
        for(int i=0;i<n;i++)q.add(a[i]);//先摘果子数量少的树
        int count=0;
        for(int i=0;i<m;i++){
            count+=b[i];
            res[i]=b[i]*q.size();//假设每天所有树都能提供想要的果子
            while(!q.isEmpty()&&count>=q.peek()){//摘的果子数量已经超过一些果树所拥有的果子
                res[i]-=(count-q.poll());//因此减去那些多摘的果子，同时果树果子耗尽出队
            }
        }
        return res;
    }
}

复杂度：
时间复杂度：将果树放入最小堆的时间复杂度为 $图片说明$ ,遍历b数组的时间复杂度为 $O(m)$ ,因此总的时间复杂度为 $图片说明$
空间复杂度:优先级队列的大小不超过n, $O(n)$
方法三：排序
也可以使用排序函数将果树按数量从小到大排序，用一个index指针指向果子数量最少的果树，每当一棵果树数量耗尽时，指针后移

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param a int整型一维数组 
     * @param b int整型一维数组 
     * @return long长整型一维数组
     */
    public long[] solve (int[] a, int[] b) {
        // write code here
        int m=b.length;
        int n=a.length;
        long[]res=new long[m];
        int[]q=new int[n];
        for(int i=0;i<n;i++)q[i]=a[i];//先摘果子数量少的树
        Arrays.sort(q);
        int count=0;
        int index=0;
        for(int i=0;i<m;i++){
            count+=b[i];//先摘果子数量少的树
            res[i]=(long)b[i]*(n-index);//假设每天所有树都能提供想要的果子
            while(index<q.length&&count>q[index]){//果子数量少的树已经没有果子了
                res[i]-=(count-q[index]);//因此减去那些多摘的果子，同时果树果子耗尽出队
                index++;
            }
        }
        return res;
    }
}

复杂度：
时间复杂度：排序函数的时间复杂度为 $图片说明$ ,遍历b数组的时间复杂度为 $O(m)$ ,因此总的时间复杂度为 $图片说明$
空间复杂度:辅助数组的大戏噢不超过n， $O(n)$