负载均衡--堆/优先队列模拟

P8755 [蓝桥杯 2021 省 AB2] 负载均衡 - 洛谷

与巧克力类似巧克力---贪心+堆模拟/优先队列-CSDN博客

#include<bits/stdc++.h>
using namespace std;
#define N 100011
typedef  long long ll;
struct no
{ll d,c;
};
struct cmp
{bool operator()(const no &a,const no &b)const{return a.c>b.c;}
};
priority_queue<no,vector<no>,cmp> pq[2*N];
ll a[2*N],n,m;
int main() {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n>>m;for(int i=1;i<=n;i++) cin>>a[i];for(int i=0;i<m;i++){ll aa,b,cc,d;cin>>aa>>b>>cc>>d;if(pq[b].size()){while(pq[b].top().c<aa&&pq[b].size()){a[b]+=pq[b].top().d;pq[b].pop();}	}if(a[b]>=d){a[b]-=d;pq[b].push({d,aa+cc-1});cout<<a[b]<<endl;}else{cout<<-1<<endl;	} }return 0;}