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

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

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

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

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

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

$最后一遍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;
}

本文地址：https://blog.csdn.net/jziwjxjd/article/details/107517136