此题需要注意2点:
1. 重载 "<" 的语义:当优先级相等时,先到的优先级高,不能指望 priority_queue 自动将先到但优先级相等的病人排在前面
2. 由于每组数据处理完之后,队列并没有 pop 空,但 priority_queue 又没有提供清空队列的方法,所以只能每组数据都重新创建对象
/**
* hdu 1873
* 【优先队列】【priority_queue】
* 此题需要注意2点:
* 1. 重载 "<" 的语义:当优先级相等时,先到的优先级高,不能指望
* priority_queue 自动将先到但优先级相等的病人排在前面
* 2. 由于每组数据处理完之后,队列并没有 pop 空,但 priority_queue 又
* 没有提供清空队列的方法,所以只能每组数据都重新创建对象
*/
#include <queue>
#include <iostream>
#include <string>
using namespace std;
struct SPatient
{
int m_iId;
int m_iPriority;
};
bool operator<(const SPatient &oPl, const SPatient &oPr)
{
if (oPl.m_iPriority == oPr.m_iPriority)
{
return (oPl.m_iId > oPr.m_iId);
}
return (oPl.m_iPriority < oPr.m_iPriority);
}
int main()
{
SPatient oTmpP;
int iCmdNum;
string strTmp;
int iDoctNum; // doctor number
int iNum;
while (cin >> iCmdNum)
{
priority_queue<SPatient> arrpqPque[3];
iNum = 0;
while (iCmdNum--)
{
cin >> strTmp;
if ('I' == strTmp[0])
{
++iNum;
cin >> iDoctNum >> oTmpP.m_iPriority;
oTmpP.m_iId = iNum;
arrpqPque[iDoctNum-1].push(oTmpP);
}
else if ('O' == strTmp[0])
{
cin >> iDoctNum;
if (arrpqPque[iDoctNum-1].empty())
{
cout << "EMPTY" << endl;
}
else
{
cout << arrpqPque[iDoctNum-1].top().m_iId << endl;
arrpqPque[iDoctNum-1].pop();
}
}
}
}
return 0;
}
getline() 和 istringstream 的注意点
/**
* hdu 1873
* 用 istringstream 处理输入
*/
#include <queue>
#include <iostream>
#include <string>
#include <sstream>
using namespace std;
struct SPatient
{
int m_iId;
int m_iPriority;
};
bool operator<(const SPatient &oPl, const SPatient &oPr)
{
if (oPl.m_iPriority == oPr.m_iPriority)
{
return (oPl.m_iId > oPr.m_iId);
}
return (oPl.m_iPriority < oPr.m_iPriority);
}
int main()
{
SPatient oTmpP;
int iCmds;
string strCmd;
istringstream issCmd;
string strTmp;
int iDoctNum; // doctor number
int iPriority;
int iNum;
while (cin >> iCmds)
{
cin.get(); // 【1】 吸收换行符,防止 getline 吸入
priority_queue<SPatient> arrpqPque[3];
iNum = 0;
while (iCmds--)
{
getline(cin, strCmd);
issCmd.clear(); // 【2】 修改标志
issCmd.str(strCmd);
if ('I' == strCmd[0])
{
++iNum;
issCmd >> strTmp >> iDoctNum >> iPriority;
oTmpP.m_iId = iNum;
oTmpP.m_iPriority = iPriority;
arrpqPque[iDoctNum-1].push(oTmpP);
}
else if ('O' == strCmd[0])
{
issCmd >> strTmp >> iDoctNum;
if (arrpqPque[iDoctNum-1].empty())
{
cout << "EMPTY" << endl;
}
else
{
cout << arrpqPque[iDoctNum-1].top().m_iId << endl;
arrpqPque[iDoctNum-1].pop();
}
}
}
}
return 0;
}