AcWing 3492. 负载均衡
原题链接
中等
作者:
辉小歌
,
2021-05-25 17:21:57
,
所有人可见
,
阅读 323
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
const int N=1e5*2+10;
struct machine
{
int id;//机器
int sum;//算力
int end;//结束的时间
friend bool operator < (machine f1,machine f2)//时间从小到大
{
return f1.end > f2.end;
}
}stu;
int sum[N];//每台计算机的当前可用的算力
int n,m;
int main(void)
{
cin>>n>>m;
priority_queue<machine> heap;
for(int i=1;i<=n;i++) scanf("%d",&sum[i]);
while(m--)
{
bool flag=false;
int a,b,c,d; scanf("%d%d%d%d",&a,&b,&c,&d);
while(heap.size())//判断可不可以释放算力
{
auto t=heap.top();
if(t.end<=a)
{
heap.pop();
sum[t.id]+=t.sum;
}
else break;
}
if(sum[b]>=d)//可以计算
{
stu.id=b,stu.sum=d,stu.end=a+c;
heap.push(stu);
sum[b]-=d;
cout<<sum[b]<<endl;
flag=true;
}
if(!flag) cout<<-1<<endl;
}
}