P8755题解

xwh_hh · 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;
}