山人前所未有地首次提交便通过 作文以记之
此题为优先队列基础题
题目乍一看可用排序 然而题目只要求输出前k个events
因此可以大致看作是partial sort 实质上来看此题体现了计算机的优先处理算法 即优先队列
难点：
Q：如何自定义优先级？
A：
struct Item{ int time, period, id; bool operator < (const Item & a) const{ return time > a.time || time == a.time && id == a.id; } };
盲点：
1. 输出时须先用一个暂时的struct(in this case, r)查找记录
2. 结构体可以多次使用
struct只是一个”模版“ 作用等同于int, char... 在程序的任何一个地方都可以重新引用
i.e.(接上一段代码)
int main(){ ... Item r; Item task; r.time+=r.period;
... }
/* Source: LA3135 Status: AC Done: 20/11/2015 Remarks: priority queue */ #include <cstdio> #include <queue> using namespace std; struct Item { int id,period,time; bool operator < (const Item &a) const{ return time > a.time || time == a.time && id > a.id; } }; char ch[10]; int main(){ priority_queue<Item> q; int id,T,k,i; Item task; while(1){ scanf("%s",ch); if(ch[0] == ‘#‘)break; scanf("%d %d",&task.id,&task.period); task.time=task.period; q.push(task); } scanf("%d",&k); for(i=1;i<=k;i++){ Item r=q.top(); printf("%d\n",r.id); q.pop(); r.time+=r.period; q.push(r); } return 0; }
文末，不忘附上启发山人的一篇好文链接：
http://www.cnblogs.com/summerRQ/articles/2470130.html
原文：http://www.cnblogs.com/peccavi/p/4981593.html