526互联

priority_queue(优先队列)

发布时间 2023-09-19 16:03:00作者: BkDench

优先队列底层模板：priority<type,container,function>,type:元素数据类型,container:容器一般是vector,
function:比较函数
优先队列默认是大根堆，即堆顶元素为最大值:定义方法为

priority_queue<type>q或priority<type,vector<type>, less<type>>q

小根堆(堆顶元素为最小值)定义方法:

priority_queue<type,vector<type>,greater<type>>q

注意：在指定排序规则时，你的排序规则需和堆的排序规则相反，比如你想让堆顶元素是最小值，那么你的排序规则需倒序
再结合小根堆，才能实现。

#include <iostream>
#include <algorithm>
#include <cstring>
#include <set>
#include <vector>
#include <map>
#include <set>
#include <cmath>
#include <queue>

//#define x first 
//#define  y second
using namespace std;

typedef long long LL;
typedef pair<LL,LL>PLL;
const int N = 200010;

LL res[N];
struct Node{
	LL time;
	int num;
	//重载>运算符
	bool operator>(const Node &b)const{
		if(this->time != b.time)return this->time > b.time;
		else return this->num > b.num;
	}
};

priority_queue<Node,vector<Node>,greater<Node>>q;

int n,m;

void init(){
	for(int i = 1; i <= n; i ++){
		q.push({0ll,i});
	}
}

int main(){
	cin >> n >> m;
	init();
	while(m --){
		int T,W,S;
		cin >> T >> W >> S;

		auto t = q.top();
		cout << t.time << " " << t.num << endl;
		q.pop();

		if(t.time <= T){
			res[t.num] = res[t.num] + W;
			LL ti = (LL)T + S;
			q.push({ti,t.num});
		}else{
			q.push(t);
		}
	}

	for(int i = 1; i <= n; i ++)cout << res[i] << endl;

	
	return 0;
}