1.题目描述：点击打开链接
2.解题思路：本题利用优先队列解决。根据题意，优先出列的是时间靠前的时间，如果当有多个事件同时发生，那么再考虑Qnum小的事件优先出列。本题有一个重要的技巧，就是每次出列后，更新一下该元素下次出列的时间，，然后再次放回队列，使得优先队列中一直都是n个元素。由于只模拟前k个时间，而STL的priority_queue的出列时间复杂度是O(logN)，因此本题的总时间复杂度是O(K*logN)。
3.代码：
#define _CRT_SECURE_NO_WARNINGS #include<iostream>#include<algorithm>#include<string>#include<sstream>#include<set>#include<vector>#include<stack>#include<map>#include<queue>#include<deque>#include<cstdlib>#include<cstdio>#include<cstring>#include<cmath>#include<ctime>#include<functional>using namespace std;struct Item{int Qnum, Period, Time;bool operator <(const Item&a)const//时间较大的放队列后面，时间相同但Qnum较大的也放队列后{return Time>a.Time || (Time == a.Time&&Qnum > a.Qnum);}};int main(){//freopen("t.txt", "r", stdin);priority_queue<Item>q;char s[20];while (~scanf("%s", s) && s[0] != '#'){Item item;scanf("%d%d", &item.Qnum, &item.Period);item.Time = item.Period;q.push(item);}int k;cin >> k;while (k–){Item r = q.top(); q.pop();printf("%d\n", r.Qnum);r.Time += r.Period;//更新下次出列的时间q.push(r);}return 0;}
想想我的影子，我会在你身后给你一个拥抱;
