首页 > 试题广场 >

牛牛港

[编程题]牛牛港

热度指数：960 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

牛牛港是牛牛国最大的港口，在这个港口里有k个码头。

牛牛港承载了牛牛国的物资装载运输任务。
目前有n个工厂告诉了牛牛港，它们物资的抵达时间和物资数量。
对于第i个工厂，它的物资抵达时间为第 $a_{i}$ 天,物资数量为 $b_{i}$ 吨，每个工厂的物资抵达的时间都是不一样的。
因为技术有限：

一个码头一天只能装载一吨的物资。
一个码头一次只能承担一个工场的物资装载任务，当完成一个任务后才能承担新的任务。
先抵达的物资，先完成装载任务。

牛牛想知道，如果合理规划，最早第几天，可以完成物资装载任务。

示例1

输入

3,2,[1,2,3],[5,5,5]

输出

示例2

输入

6,1,[4,2,5,3,1,6],[10,10,10,10,10,3]

输出

备注:

两个整数：n，k()
一个数组a：()
一个数组b：()
工场下标从0开始

算法知识视频讲解

C/C++

nbgao

typedef long long ll;
class Solution {
public:
    /**
     * 
     * @param n int整型 
     * @param k int整型 
     * @param a int整型vector 
     * @param b int整型vector 
     * @return long长整型
     */
    long long solve(int n, int k, vector<int>& a, vector<int>& b) {
        priority_queue<ll, vector<ll>, greater<ll>> Q;
        vector<int> c(n);
        for(int i=0;i<n;i++)
            c[i] = i;
        sort(c.begin(), c.end(), [&a](int x, int y){return a[x]<a[y];});
        for(auto &x: c){
            while(!Q.empty() && a[x]>=Q.top())
                Q.pop();
            if(Q.size()<k)
                Q.push(a[x]+b[x]);
            else{
                Q.push(Q.top()+b[x]);
                Q.pop();
            }
        }
        while(Q.size()>1)
            Q.pop();
        return Q.top();
    }
};

发表于 2020-07-19 03:39:36 回复(0)

麻麻我想要offer

实例1的11是怎么得出来的？

发表于 2020-07-29 11:56:17 回复(1)

0x105

#include<bits/stdc++.h>

using namespace std;
typedef long long LL;
class Solution {
public:
    long long solve(int n, int k, vector<int>& a, vector<int>& b) {
        // write code here
        vector<int> idx(n);
        for(int i = 0; i < n; i++) {
            idx[i] = i;
        }
        sort(idx.begin(), idx.end(), [&a] (int x, int y) {return a[x] < a[y];});
        //用小顶堆按完成顺序保存任务完成时间
        priority_queue<LL ,vector<LL>, greater<LL>> time;
        //按时间顺序对每个工厂的货物
        for(int i = 0; i < n; i++) {
            //完成的任务出队
            while(!time.empty() && a[idx[i]] >= time.top()) time.pop();
            //如果有空的码头,直接把任务分配给空的码头,结束时间是到达天数+耗时天数
            if(time.size() < k) {
                time.push(b[idx[i]] + a[idx[i]]);
            } else {
               //没有空的码头，重新计算结束时间**队，并把当前最先结束任务出队。结束时间为 当前最先结束任务的结束时间+ 耗时天数
                time.push(b[idx[i]] + time.top());
                time.pop();
            }
        }
        //留下最后一个任务
        while(time.size() > 1) time.pop();
        return time.top();
    }
};

发表于 2020-07-16 20:45:32 回复(0)

C/C++

刘禅挥泪斩孔明

题目虽然说“合理规划”，但是其实没有什么规划的空间，因为规则里定死了先来的先卸货，然后所有的货物到达的时间又都不同，所以用优先队列模拟即可。

class Solution {
    typedef long long int64;
    struct cmp {
        vector<int> const& a;
        cmp(vector<int> const& A): a(A) {}
        bool operator()(int x, int y) const { return a[x] < a[y];}
    };
public:
    /**
     * 
     * @param n int整型 
     * @param k int整型 
     * @param a int整型vector 
     * @param b int整型vector 
     * @return long长整型
     */
    int64 solve(int n, int k, vector<int> const& a, vector<int>const& b) {
        // write code here
        vector<int> goods(n);
        for (int i = 0; i < n; i++) goods[i] = i;
        sort(goods.begin(), goods.end(), cmp(a));
        priority_queue<int64, vector<int64>, greater<int64> > h;
        for (int i = 0; i < n; i++) {
            while (h.size() && a[goods[i]] >= h.top()) h.pop();
            if (h.size() < k) h.push(b[goods[i]] + a[goods[i]]);
            else h.push(b[goods[i]] + h.top()), h.pop();
        }
        while (h.size() > 1) h.pop();
        return h.top();
    }
};

发表于 2020-03-31 19:10:01 回复(1)