自动搬运

查看原文

来自洛谷，原作者为

	xwh_hh 以上材料引发了你怎样的联想和思考？请写一篇文章，文体不限，cpp除外。

搬运于2025-08-24 22:42:08，当前版本为作者最后更新于2023-07-18 18:25:08，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

一道经典好题。

我们可以考虑用 $n$ 个堆去维护在各个计算机中运行的程序，每当有一个任务 $(a_i,b_i,c_i,d_i)$ 被指派时，我们就可以先将已完成的任务删除，再判断算力是否能够承受，这样每个任务入堆后平均只会被访问 $2$ 次，节省了很多时间。

由于同一台计算机中，早完成的任务一定比晚完成的任务先删除，这让我们想到了小根堆。我们希望在弹出时能够立即知道算力，所以我们可以用 pair 类型的小根堆来维护，first 维护结束时间，second 维护占用算力，时间复杂度 $O(m\log n)$。

上代码：

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;//结束时间first 占用算力second
int n,m,h[200005];
priority_queue<P,vector<P>,greater<P> > pq[200005];//堆 
int main() {
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>h[i];
    while(m--){
        int a,b,c,d;
        cin>>a>>b>>c>>d;
        while(!pq[b].empty() && pq[b].top().first<=a){//将已完成的任务删除 
            h[b]+=pq[b].top().second;
            pq[b].pop();
        }
        if(h[b]<d) cout<<-1<<endl;
        else{//分配 
            h[b]-=d;
            pq[b].push(P(a+c,d));//注意是结束时间 
            cout<<h[b]<<endl;
        }
	} 
    return 0;
}