负载均衡

用优先队列实现小根堆

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
const int N = 200010;
#define x first
#define y second
typedef pair<int,int>PII;  //记录每个任务分配之后的结束时间和所需算力
priority_queue<PII,vector<PII>,greater<PII> >q[N]; //转化为大根堆
int s[N];  //表示每个计算机的算力

int n,m;
int main()
{
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++) scanf("%d",&s[i]);
    while (m--)
    {
        int a,b,c,d;
        scanf("%d%d%d%d",&a,&b,&c,&d);
        //当前面任务结束的时间小于新任务开始的时间，前面的任务就可以删掉了
        while (q[b].size()&&q[b].top().x<=a)  //作用是去掉前面已经完成的任务
        {
            s[b]+=q[b].top().y; //恢复算力
            q[b].pop();  //这个任务可以删除了，已经完成了
        }
        if (s[b]<d) puts("-1");  //当前的计算机算力小于所需算力，无法分配
        else  //否则表示可以分配
        {
            q[b].push({a+c,d});  //分配之后的任务结束时间是当前时间加所需时间
            s[b]-=d; //相应计算机算力减去
            printf("%d\n",s[b]);  //输出表示这个计算机可以完成所分配的任务
        }
    }
}