P2278 [HNOI2003]操作系统(模拟,优先队列)

$一开始没有进程, 加入第一个进程, 记此时的时间为 t i m 一开始没有进程,加入第一个进程,记此时的时间为tim$

$然后拿出第二个进程, 算出第二个进程和 t i m 的差值记作 s h i 然后拿出第二个进程,算出第二个进程和tim的差值记作shi$

$那么每次从优先队列拿一个优先级最高的进程来做那么每次从优先队列拿一个优先级最高的进程来做$

$这个进程如果在 s h i 之内做完, 更新 s h i 和 t i m 的值, 弹出队列这个进程如果在shi之内做完,更新shi和tim的值,弹出队列$

$这个进程如果在 s h i 之内做不完, 更新 t i m 的值, 再放回队列这个进程如果在shi之内做不完,更新tim的值,再放回队列$

$最后一遍 w h i l e 循环, 每次拿出优先级最高的, 一直做完最后一遍while循环,每次拿出优先级最高的,一直做完$

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
struct node{
	int num,beg,t,impor;
	bool operator < (const node&tmp )const{
		if( impor!=tmp.impor )	return impor<tmp.impor;
		return beg>tmp.beg;
	}
}a[500009];
priority_queue<node>q;
typedef pair<int,int>p;
vector<p>vec;
int main()
{
	std::ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int x,w,e,r,top=0;
	while( cin>>x>>w>>e>>r )
		a[++top] = (node){x,w,e,r} ;
	q.push( a[1] );
	int tim=a[1].beg;
	for(int i=2;i<=top;i++)
	{
		while( !q.empty() )
		{
			node u=q.top(); q.pop();
			int shi=a[i].beg-tim;
			if( shi<u.t )
			{
				u.t-=shi;q.push(u);
				tim=a[i].beg;
				break;
			}
			else
			{
				tim+=u.t;
				vec.pb( p(u.num,tim) );
			}
		}
		if( q.empty() )	tim=a[i].beg;//队列为空!,那么需要更新tim了 
		q.push( a[i] );
	}
	while( !q.empty() )
	{
		node u=q.top(); q.pop();
		tim+=u.t;
		vec.pb( p(u.num,tim) );
	}
	for(int i=0;i<vec.size();i++)
		cout << vec[i].first << " " << vec[i].second << endl;
}