题目来源

2021年蓝桥省赛第二场I题

题目链接：http://acm.mangata.ltd/p/P1480

考点

优先队列、模拟

视频讲解

https://www.bilibili.com/video/BV1ST4y117fs

思路

因为有n台计算机，所以我们可以开一个数组V，V[i]表示第i台机器的算力大小，考虑到一个任务是在第a[i]时刻开始到a[i]+c[i]结束的，所以我们得想办法记录下来，但是都记录吗？咱们NO，其实每当一个任务来临得时候，我们只需要看看指定的这一台计算机有哪些任务以及结束了，由于a数组（时间）是严格升序的，我们会发现只需要记录下结束的时间即可，我们每次有一个任务来临我们就把之前任务的算力释放出来，那么我们应该从最早结束的任务开始查看，如果以及结束了，那么我们就释放，然后看下一个任务，如果没有结束，那么后面的任务都不会在当前时刻结束，然后我们就能计算出当前还剩下多少算力，然后和当前这个任务进行判断如果能执行，那么继续放在我们的这个任务序列中

现在的问题就变成了，我们怎么维护每个计算机的任务序列，我们很容易能想到堆，用一个小顶堆来维护，因为我们的任务结束时间需要升序，STL已经帮我们实现好了也就是priority_queue即优先队列，然后我们每个任务除了结束时间，我们还应该知道这个任务的算力，因为我们要释放算力，这里我们可以直接使用pair<int,int>或者使用自定义结构体，但是结构体需要自己写重载，所以我这里推荐大家使用pair。那么我们就来写代码吧！

代码

#include<bits/stdc++.h>
using namespace std;
//----------------自定义部分----------------
#define ll long long
#define mod 1000000009
#define endl "\n"
#define PII pair<int,int>

int dx[4]={0,-1,0,1},dy[4]={-1,0,1,0};

ll ksm(ll a,ll b) {
	ll ans = 1;
	for(;b;b>>=1LL) {
		if(b & 1) ans = ans * a % mod;
		a = a * a % mod;
	}
	return ans;
}

ll lowbit(ll x){return -x & x;}

const int N = 2e5+10;
//----------------自定义部分----------------
int n,m,q,a,b,c,d,V[N];
priority_queue<PII,vector<PII>,greater<PII> > que[N];//维护n台电脑的小顶堆

int main()
{
	cin>>n>>m;
	for(int i = 1;i <= n; ++i) cin>>V[i];//输出算力 
	for(int i = 0;i < m; ++i) {
		cin>>a>>b>>c>>d;
		while(que[b].size()){
			int ed = que[b].top().first;//当前最先结束的任务的时间
			int kk = que[b].top().second;//当前最先结束的任务的算力
			if(ed > a) break;//如果当前任务结束时间大于当前时间，后面的任务肯定都大于
			V[b] += kk;
			que[b].pop();
		}
		if(V[b] < d){//如果当前的算力不足，那么直接输出-1
			cout<<"-1"<<endl;
		}
		else{//如果当前的算力充足，那么就把这个任务放入b计算机的队列中
			que[b].push({a+c,d});
			V[b] -= d;
			cout<<V[b]<<endl;
		}
	}
	
	return 0;
}
/*
2 6
5 5
1 1 5 3
2 2 2 6
3 1 2 3
4 1 6 1
5 1 3 3
6 1 3 4
*/

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
// #define x first
// #define y second
const int N=2e5+10;
int n,m;
int s[N];//每台计算机的算力
// typedef pair<int,int> PII;//<结束时刻,算力>
// priority_queue<PII,vector<PII>,greater<PII> > q[N];//每台计算机任务
//greater 升序，小根堆；less 降序，大根堆
struct PII{
    int x,y;
    bool operator>(const PII &s) const{
        if(x>s.x || (x==s.x&&y>s.y))
            return true;
        else
            return false;
    }
};
priority_queue<PII,vector<PII>,greater<PII> > q[N];

int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		cin>>s[i];
	for(int i=1;i<=m;i++){
		int a,b,c,d;
		cin>>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)
			cout<<"-1";
		else{
			q[b].push({a+c,d});//a+c:开始时刻+持续时间->结束时间
			s[b]-=d;
			cout<<s[b];
		}
		cout<<endl;
	}
}

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII; 
const int N = 2e5+5;
int n, m;
int a,b,c,d,s[N];
priority_queue<PII, vector<PII>, greater<PII>> q[N]; 
int main()
{
    ios::sync_with_stdio(false);
	cin>>n>>m;
	for (int i=1;i<=n;i++) cin>>s[i];
	while(m--)
	{
		cin>>a>>b>>c>>d;
		while (!q[b].empty()&&q[b].top().x<=a)
		{
			s[b]+=q[b].top().y;
			q[b].pop();
		}
		if (s[b]>=d) {
			q[b].push({a+c,d});
			s[b]-=d;
			cout<<s[b]<<endl;
		}
		else cout<<-1<<endl;
	}
	return 0;
}

用优先队列来维护每一台电脑的状态即可

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
inline int read(){//快读
	char ch=getchar();
	int f=1,c=0;
	while(ch<'0'||ch>'9'){
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		c=(c<<1)+(c<<3)+(ch^48);
		ch=getchar();
	}
	return c*f;
}
typedef pair<int, int> Pii;
const int N = 200010;
int n, m;
int s[N];
priority_queue<Pii, vector<Pii>, greater<Pii> > q[N];//N代表不同的计算机
int main()
{
	n=read(),m=read();
	for(int i = 1;i<=n;i++){
		s[i]=read();
	}	
	while (m--){
		int a,b,c,d;
		a=read(),b=read(),c=read(),d=read();
		while(!q[b].empty()&&q[b].top().x<=a){//对于截止时间在a之前的统统处理掉
			s[b]+=q[b].top().y;//那么相应的计算机能力也将回复
			q[b].pop();
		}
		if(s[b]<d) cout<<"-1\n";
		else{
			q[b].push(make_pair(a+c,d));//加入当前的任务
			s[b]-=d;//减去当前任务消耗的计算能力
			printf("%d\n",s[b]);
		}
	}
	return 0;
}