1.首先解释一下大根堆小根堆的表示方法:
priority_queue<int> a; //等同于 priority_queue<int, vector<int>, less<int> > a; 当然也可以定义小根堆:
priority_queue<int, vector<int>, greater<int> > c; //这样就是小顶堆
也可以将pair加入到其中:
将pair加入到队列中: priority_queue<pair<int, int> > a;//先比较first 再比较second 对于优先队列的操作: top 访问队头元素 empty 队列是否为空 size 返回队列内元素个数 push 插入元素到队尾 (并排序) emplace 原地构造一个元素并插入队列 pop 弹出队头元素 swap 交换内容
题目:
代码:
#include<iostream> #include<cstring> #include<cmath> #include<cstdio> #include<algorithm> #include<queue> using namespace std; typedef pair<int, int> PII; const int maxx=2e6+10; int v[maxx]; priority_queue<PII, vector<PII>, greater<PII> > p[maxx];//结束时刻,算力 int main(){ int n,m; scanf("%d %d",&n,&m); for(int i=1;i<=n;i++){ scanf("%d",&v[i]); } for(int i=0;i<m;i++){ int a,b,c,d; scanf("%d %d %d %d",&a,&b,&c,&d); while(p[b].size()&&p[b].top().first<=a){ v[b]+=p[b].top().second; p[b].pop(); }//在中间是不是可以恢复一部分算力不重要 重要的是能不能开始 if(v[b]>=d){ printf("%d\n",v[b]-d); p[b].push({a+c,d});//存入的应该是当前任务消耗的算力,不是现在的算力 v[b]-=d; }else{ printf("-1\n"); } } }