题意参见:http://acm.pku.edu.cn/JudgeOnline/problem?id=2051
其实这个题目可以理解成os上的进程调度:有一些进程,每个进程有一个唯一的id和一个执行周期(每隔一个执行周期,进程就要执行一次)。要求把前t次执行的进程的id输出来,如果多个进程同一时刻执行,那么按照进程升序输出。
该问题可以用优先队列直接解决,下面是AC代码,优先队列直接使用了STL的priority_queue。
#include"iostream"
#include "stdio.h"
#include"queue"
#include "algorithm"
using namespace std;
//任务类,可以理解成os中的一个进程
class Task
{
public:
friend ostream& operator<<(ostream& os,const Task& a)
{
os<<a.m_Id<<" "<<a.m_Period;
return os;
}
Task(int id,int period):m_Period(period),m_Id(id),m_RunTime(period)
{
}
//任务执行(啥都不做,呵呵),并计算出下一次任务应该执行的时间
void Run()
{
this->m_RunTime +=this->m_Period;
}
inline int GetId()const
{
return this->m_Id;
}
inline int GetPeriod()const
{
return this->m_Period;
}
inline long GetRunTime()const
{
return this->m_RunTime;
}
private:
int m_Period; //任务的周期,代表该任务每隔m_Period就必须执行一次
int m_Id; //任务的id
long m_RunTime; //任务执行的时间,最初时刻:m_RunTime = m_Period,以后每次执行之后再更新
};
class compare
{
public:
bool operator ()(const Task& a,const Task& b)
{
if (a.GetRunTime() < b.GetRunTime())
{
return false;
}
else if (a.GetRunTime() == b.GetRunTime())
{
return a.GetId()>b.GetId();
}
else
{
return true;
}
}
};
int main(void)
{
priority_queue<Task,vector<Task>,compare> priq;
char a[10];
int id,period;
int n;
while(scanf("%s",&a),a[0] !='#')
{
scanf(" %d %d",&id,&period);
priq.push(Task(id,period));
}
scanf("%d",&n);
while(n--)
{
Task t = priq.top();
t.Run();
cout<<t.GetId()<<endl;
priq.pop();
priq.push(t);
}
return 0;
}