描述

这是一篇面对初级coder的题解。

知识点： 堆 数学 模拟

难度： 三星

题解

题目：

有n棵苹果树，第i棵苹果树上有$a_{i}a\_\{i\}$ai​个果子。 计划$mm$m天去采摘果子。对于第$ii$i天，它会去所有果树上轮流采摘$b_{i}b\_\{i\}$bi​个果子。如果对于第i天，某棵果树上没有$b_{i}b\_\{i\}$bi​个果子，那么它只会把当前果树上的果子采摘完。 返回一个数组 （代表每一天的真实苹果采摘量）

分析：

模拟的逻辑如下图

需要先对果树进行排序，从而优化查找速度

方法一：暴力求解

双重遍历：

第一轮：遍历每一天，摘对应的苹果

第二轮：遍历每一棵树，通过预先按果子数进行排序，可以每次从不为空的树开始维护，从而提高搜索效率。

class Solution {
public:
    vector<long> solve(vector<int>& a, vector<int>& b) {
        vector<long> ans(b.size(),0);//返回答案数组
        sort(a.begin(),a.end());//按苹果由少到多排序
        int begin=0;//记录摘到苹果
        for(int i=0;i<b.size();i++){//遍历每一天
            for(int j=begin;j<a.size();j++){//遍历每棵树
                if(a[j]<=b[i]){//不够摘
                    ans[i]+=a[j];//只摘当前值
                    a[j]=0;
                    begin=j+1;//下次遍历从不为空的树开始
                }
                else{
                    ans[i]+=b[i];//摘预定值
                    a[j]-=b[i];//树上果子减摘取值
                }
            }
        }
        return ans;
    }
};

运行测试：

2/8 组用例通过 运行时间1001ms 占用内存308KB

复杂度分析：

时间复杂度：最坏情况下$O(nlongn+mn)O(nlongn+mn)$O(nlongn+mn)，sort排序$O\left(nlongn\right)O(nlongn)$O(nlongn)，加上主程序两层循环相互嵌套

空间复杂度：$O\left(1\right)O(1)$O(1)，不占用额外存储空间，其中ans是返回函数必要空间，不属于额外空间

方法一改：排序 记录

优化上述方法，上述方法在每次采摘中需要实时维护每棵树上的果子数，而事实上，这个值无需输出，可以采用懒标记的形式维护，而当树上果子够摘时，可以直接用乘法计算结果，提高效率。

主要优化点：统一采用一个已摘取值来记录，无需维护每棵树上的果子数，排序后后面的树不再遍历

class Solution {
public:
    vector<long> solve(vector<int>& a, vector<int>& b) {
        vector<long> ans(b.size(),0);//返回答案数组
        sort(a.begin(),a.end());//按苹果由少到多排序
        int begin=0;//标记开始位
        long done=0; //已采摘
        for(int i=0;i<b.size();i++){//遍历每一天
            done+=b[i];
            for(int j=begin;j<a.size();j++){//遍历每棵树
                if(a[j]<=done){//不够摘
                    ans[i]+=a[j]-(done-b[i]);//只摘当前值
                    begin=j+1;//下次遍历从不为空的树开始
                }
                else{
                    ans[i]+=b[i]*(a.size()-j);//后面的树全部摘预定值
                    break;
                }
            }
        }
        return ans;
    }
};

运行测试：

运行时间 51ms 占用内存 6720KB

复杂度分析：

时间复杂度：最坏情况下$O(nlongn+m+n)O(nlongn+m+n)$O(nlongn+m+n)，sort排序$O\left(nlongn\right)O(nlongn)$O(nlongn)，主程序两层循环虽然相互嵌套，但是每次只找到不够摘的树就跳出，姑为$O(m+n)O(m+n)$O(m+n)

空间复杂度：$O\left(1\right)O(1)$O(1)，不占用额外存储空间，其中ans是返回函数必要空间，不属于额外空间

方法二：堆

采用一个堆来维护苹果树，每次将不够摘的树移出堆，从而保证每个树只进出堆一次。

同时需要记录已摘的果子数，当堆顶果树值小于此值，则令其出堆

每次返回值=（出堆果子数-之前已摘总数）——可能有多个+ 堆大小*本日应采摘值

class Solution {
public:
    vector<long> solve(vector<int>& a, vector<int>& b) {
        vector<long> ans(b.size(),0);
        sort(a.begin(),a.end());
        priority_queue<int, vector<int>, greater<int>> apple; //小顶堆苹果园
        long done=0; //已采摘
        for(int i=0;i<a.size();i++)//所有果树入堆
            apple.push(a[i]);
        for(int i=0;i<b.size();i++){//开始摘果子
            done+=b[i];//每棵树总计果量
            ans[i]=apple.size()*b[i];//假设全部够摘
            while(apple.size()!=0&&apple.top()<done){
                ans[i]-=done-apple.top();//减去不够摘的部分
                apple.pop();//出堆
            }
        }
        return ans;
    }
};

复杂度分析：

时间复杂度：最坏情况下$O(nlongn+m+n)O(nlongn+m+n)$O(nlongn+m+n)，堆排序$O\left(nlongn\right)O(nlongn)$O(nlongn)，主程序两层循环虽然相互嵌套，但是每次只找到不够摘的树就跳出，故为$O(m+n)O(m+n)$O(m+n)

空间复杂度：$O\left(n\right)O(n)$O(n)，占用额外存储空间（堆的长度）

运行测试：

运行时间 60ms 占用内存 6980KB

总结

可以采用堆的结构来维护有序数组 ——如c++中提供的priority_queue

堆排序

　　堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序，它的最坏，最好，平均时间复杂度均为O(nlogn)，它也是不稳定排序。

　　堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。如下图：