描述

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

知识点： 堆 模拟

难度： 三星

题解

题目：

牛牛港有k个码头 目前有n个工厂对于第i个工厂，它的物资抵达时间为第$a_{i}a\_\{i\}$ai​天,物资数量为$b_{i}b\_\{i\}$bi​吨 一个码头一天只能装载一吨的物资。一个码头一次只能承担一个工场的物资装载任务，当完成一个任务后才能承担新的任务。先抵达的物资，先完成装载任务。 求最早第几天，可以完成物资装载任务？

分析：

本题可以用贪心的方式求解 先到先得，关键在于维护港口的队列，最快找到空的/最快结束的港口，港口队列中的值代表当前港口的累计完成卸货时间。

方法一：暴力求解

双重遍历，采用类似冒泡的形式找到合适的港口

第一轮遍历：遍历所有货物

第二轮遍历：为当前货物寻找合适的港口 若到达日期大于卸货完成日期——直接更新港口日期=当前货物到达日期+当前货物卸货完成日期 否则找到当前最早完成卸货港口 更新港口日期=港口卸货完成日期+当前货物卸货完成日期

#include <stdint.h> 
struct target {//存储状态
    int date;//时间
    int num;//仓储量
};
bool cmp(target a, target b){//自定义比较函数 便于排序
    return a.date<b.date;//按到达时间由大到小排序
}
class Solution {
public:
    long long solve(int n, int k, vector<int>& a, vector<int>& b) {
        vector<target> target(n);//待排序目标分值
        for(int i=0;i<n;i++){
            target[i].date=a[i];//时间
            target[i].num=b[i];//货物量
        }
        sort(target.begin(), target.end(),cmp);//排序
        vector<long long> gang(k,0);//港口
        int i,j;
        for(i=0;i<n;i++){//遍历所有货物
            long long min=INT64_MAX;//最小值
            int minnum=0;
            for(j=0;j<k;j++){
                if(gang[j]<=target[i].date){//如果有合适的港口，直接入港
                    gang[j]=target[i].date+target[i].num;//
                    break;
                }
                if(min>gang[j]){//寻找最小值
                    min=gang[j];
                    minnum=j;
                }
            }
            if(j==k)//遍历一遍，无合适港口
                gang[minnum]+=target[i].num;//等待用时最短港口
        }
        long long max=0;
        for(int j=0;j<k;j++){//返回最大值的港口
            if(max<gang[j])
                max=gang[j];
            }
        return max;
        // write code here
    }
};

复杂度分析：

时间复杂度：$O\left(nk\right)O(nk)$O(nk) 最坏情况下，需要连续两轮遍历，循环套循环，时间复杂度是$O\left(nk\right)O(nk)$O(nk)。

空间复杂度：$O\left(n\right)O(n)$O(n),由于最多有n个工厂入队列，需要额外大小为n的队列，所以空间复杂度是$O\left(n\right)O(n)$O(n)。

运行测试：

4/9 组用例通过

运行时间 1001ms 占用内存 6464KB

方法二：堆

分析：在上一个方法中，每次遍历港口找到最小值占用了很多时间，

故采用堆的形式来维护港口序列每次只需要判断最小堆堆顶值和堆大小即可确定可以卸货的港口

同 https://blog.nowcoder.net/n/f5ed77ad4a5f409c9597f622080fa7e8 采用堆的结构来维护有序数组 ——c++中提供的priority_queue

最后将堆中元素逐个出堆 即可得到最长卸货时间。

struct target {//存储状态
    int date;//时间
    int num;//仓储量
};
bool cmp(target a, target b){//自定义比较函数 便于排序
    return a.date<b.date;//按到达时间由大到小排序
}
class Solution {
public:
    long long solve(int n, int k, vector<int>& a, vector<int>& b) {
        vector<target> target(n);//待排序目标分值
        for(int i=0;i<n;i++){
            target[i].date=a[i];//时间
            target[i].num=b[i];//货物量
        }
        sort(target.begin(), target.end(),cmp);//排序
        priority_queue<long long, vector<long long>, greater<long long>> gang;//港口
        for(int i=0;i<n;i++){//遍历所有货物
            while(gang.size()!=0&&target[i].date>=gang.top())//卸货完成
                gang.pop();
            if(gang.size()<k)
                gang.push(target[i].date+target[i].num);//利用空港口
            else{
                gang.push(gang.top()+target[i].num);//等待港口
                gang.pop();//旧港口出堆
            }
        }
        while(gang.size() > 1)
            gang.pop();//只剩最后一个港口
        return gang.top();
    }
};

复杂度分析：

时间复杂度：$O\left(nlogn\right)O(nlogn)$O(nlogn) 对于堆排序，由于最多有n个工厂入堆，每次插入和删除的时间复杂度是$O\left(logn\right)O(logn)$O(logn)。

空间复杂度：$O\left(n\right)O(n)$O(n),由于最多有n个工厂入堆，需要额外大小为n的堆，所以空间复杂度是$O\left(n\right)O(n)$O(n)。

运行测试：

运行时间 85ms 占用内存 6772KB

总结

堆排序

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

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