题解 | #牛牛港#

牛牛港

http://www.nowcoder.com/practice/809baa62665446e08ac93a16791c0094

题意整理

  • 有n个工厂,提供了抵达时间和物资数量,由于每天只能装载一天,所以物资数量也相当于停留时间。
  • 按先抵达的工厂先装载的规则,通过k个码头最少多少天完成装载任务。

方法一(排序+小顶堆)

1.解题思路

  • 首先将工厂按抵达时间排好。
  • 然后遍历所有工厂,如果某个工厂已经装载完毕,则从堆中移除。如果正在装载的工厂不足k个,说明还有空余的码头没有使用,直接将抵达时间+消耗时间放到堆里;如果达到k个,则需要等待堆顶的那个工厂装载完,将堆顶时间+消耗时间放到堆里,并且移除堆顶的工厂。
  • 最后取出堆中最大的元素,即是最后一个工厂的装载结束时间。

动图展示:
图片说明

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @param k int整型 
     * @param a int整型一维数组 
     * @param b int整型一维数组 
     * @return long长整型
     */
    public long solve (int n, int k, int[] a, int[] b) {
        //用于存放工厂id和抵达时间
        int[][] arr=new int[n][2];
        for(int i=0;i<n;i++){
            arr[i][0]=i;
            arr[i][1]=a[i];
        }
        //按抵达时间排序
        Arrays.sort(arr,(o1,o2)->o1[1]-o2[1]);

        //初始化小顶堆
        PriorityQueue<Long> queue=new PriorityQueue<>();
        for(int i=0;i<n;i++){
            int id=arr[i][0];
            //如果某个工厂已经装载完毕,则从堆中移除
            while(!queue.isEmpty()&&a[id]>=queue.peek()){
                queue.poll();
            }
            //如果正在装载的工厂不足k个,则直接将抵达时间+消耗时间放到堆里
            if(queue.size()<k){
                queue.offer((long)a[id]+b[id]);
            }
            //如果达到k个,则需要等待堆顶的那个工厂装载完
            else{
                queue.offer(queue.peek()+b[id]);
                queue.poll();
            }
        }

        //取出堆中最大的元素,即是最后一个工厂的装载结束时间
        while(queue.size()>1){
            queue.poll();
        }
        return queue.peek();

    }
}

3.复杂度分析

  • 时间复杂度:最多n个工厂入堆,每次插入和删除的时间复杂度是,所以最终的时间复杂度是
  • 空间复杂度:需要额外大小为n的小顶堆,所以空间复杂度是

方法二(TreeMap+小顶堆)

1.解题思路

  • 首先初始化小顶堆,并将k个工厂预先放入堆。
  • 然后初始化map,将抵达时间作为key,消耗时间作为value放入map,保证按抵达时间排好
  • 遍历所有工厂,如果抵达时间大于等于某个工厂的结束任务时间,直接将抵达时间+消耗时间入堆;如果小于,则将堆顶时间+消耗时间入堆。
  • 最后取出堆中最大的元素,即是最后一个工厂的装载结束时间。

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 
     * @param n int整型 
     * @param k int整型 
     * @param a int整型一维数组 
     * @param b int整型一维数组 
     * @return long长整型
     */
    public long solve(int n, int k, int[] a, int[] b) {
        //初始化小顶堆,并将k个工厂预先放入堆
        PriorityQueue<Long> queue=new PriorityQueue<>();
        for(int i=0;i<k;i++){
            queue.add(1L);
        }
        //初始化map,将抵达时间作为key,消耗时间作为value放入map
        TreeMap<Integer,Integer> map=new TreeMap<>();
        for(int i=0;i<n;i++){
            map.put(a[i],b[i]);
        }
        for(Map.Entry<Integer,Integer> entry:map.entrySet()){
            Integer day=entry.getKey();
            Integer duration=entry.getValue();
            Long poll=queue.poll();
            //如果抵达时间大于等于某个工厂的结束任务时间,直接将抵达时间+消耗时间入堆
            if(day>=poll){
                queue.add(Long.valueOf(day+duration));
            }
            //如果小于,则将堆顶时间+消耗时间入堆
            else{
                queue.add(poll+duration);
            }
        }
        //取出堆中最大的元素,即是最后一个工厂的装载结束时间
        while(queue.size()>1){
            queue.poll();
        }
        return queue.peek();
    }
}

3.复杂度分析

  • 时间复杂度:最多n个工厂入堆,每次插入和删除的时间复杂度是,所以最终的时间复杂度是
  • 空间复杂度:需要额外大小为n的小顶堆和TreeMap,所以空间复杂度是
xqxls的题解 文章被收录于专栏

牛客题解

全部评论

相关推荐

不愿透露姓名的神秘牛友
07-08 14:10
点赞 评论 收藏
分享
Yki_:你要算时间成本呀,研究生两三年,博士三四年,加起来就五六年了,如果你本科去腾讯干五年,多领五年的年薪,加上公司内涨薪,可能到时候十五年总薪资也跟博士差不多
点赞 评论 收藏
分享
Twilight_m...:表格简历有点难绷。说说个人看法: 1.个人基本情况里好多无意义信息,什么婚姻状况、健康状况、兴趣爱好、户口所在地、身份证号码、邮政编码,不知道的以为你填什么申请表呢。 2.校内实践个人认为对找工作几乎没帮助,建议换成和测开有关的项目,实在没得写留着也行。 3.工作经历完全看不出来是干什么的,起码看着和计算机没啥关系,建议加强描述,写点你在工作期间的实际产出、解决了什么问题。 4.个人简述大而空,看着像AI生成,感觉问题最大。“Python,C,C++成为我打造高效稳定服务的得力工具”、“我渴望凭借自身技术知识与创新能力,推动人工智能技术的应用发展,助力社会实现智能化转型”有种小学作文的美感。而且你确定你个人简述里写的你都会嘛?你AI这块写的什么“深入研究”,发几篇顶会的硕博生都不一定敢这么写。而且你AI这块的能力和软测也完全无关啊。个人简述建议写你对哪些技术栈、哪些语言、哪些生产工具的掌握,写的有条理些,而且最好是和测开强相关的。
点赞 评论 收藏
分享
今天 11:15
中南大学 Java
好可爱的hr姐姐哈哈哈哈
黑皮白袜臭脚体育生:兄弟们貂蝉在一起,吕布开了
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务