HDU - 1873 看病要排隊 (優先隊列)

點我看題

題意:看病排隊,首先根據病情的輕重緩急來醫治,嚴重的先治,病情相同的情況下,先來的先治,根據輸入輸出病人的id.

分析:就是一個優先隊列進隊出隊的問題,關鍵在于優先隊列的重載小于号.

參考代碼:

#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<queue>
#include<iostream>

using namespace std;
int n;
struct Node{
	int id;
	int val;
	friend bool operator < ( const Node &a, const Node &b)
	{
		if( a.val != b.val)//從小到大
			return a.val < b.val;
		return a.id > b.id;//從大到小
	}
};
priority_queue<Node> q1;
priority_queue<Node> q2;
priority_queue<Node> q3;

int main()
{
	while( ~scanf("%d",&n))
	{
		while( !q1.empty())
			q1.pop();
		while( !q2.empty())
			q2.pop();
		while( !q3.empty())
			q3.pop();

		int cnt = 0;
		while( n--)
		{
			char str[10];
			int a,b;
			scanf("%s",str);
			if( !strcmp("IN",str))
			{
				cnt++;
				scanf("%d%d",&a,&b);
				Node tmp;
				tmp.id = cnt;
				tmp.val = b;
				if( a == 1)
					q1.push(tmp);	
				else if( a == 2)
					q2.push(tmp);
				else
					q3.push(tmp);
			}
			else if( !strcmp("OUT",str))
			{
				Node tmp;
				scanf("%d",&a);
				if( a == 1 && !q1.empty())
				{
					tmp = q1.top();
					printf("%d\n",tmp.id);
					q1.pop();
				}
				else if( a == 2 && !q2.empty())
				{
					tmp = q2.top();
					printf("%d\n",tmp.id);
					q2.pop();	
				}
				else if( a == 3 && !q3.empty())
				{
					tmp = q3.top();
					printf("%d\n",tmp.id);
					q3.pop();
				}
				else
					puts("EMPTY");
			}
		}
	}

	return 0;
}