欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  移动技术

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

程序员文章站 2022-03-29 18:39:31
一开始没有进程,加入第一个进程,记此时的时间为tim一开始没有进程,加入第一个进程,记此时的时间为tim一开始没有进程,加入第一个进程,记此时的时间为tim然后拿出第二个进程,算出第二个进程和tim的差值记作shi然后拿出第二个进程,算出第二个进程和tim的差值记作shi然后拿出第二个进程,算出第二个进程和tim的差值记作shi那么每次从优先队列拿一个优先级最高的进程来做那么每次从优先队列拿一个优先级最高的进程来做那么每次从优先队列拿一个优先级最高的进程来做这个进程如果在shi之内做完,更新shi和...

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

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

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

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

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

while,,最后一遍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

相关标签: 神仙思维题