桐桐的新闻系统

桐桐为期末的计算机作业设计了一套新闻系统，他把这套新闻系统称为 Argus。使用这套系统的用户可以向这套系统注册，然后这套系统就会以用户要求发送新闻的时间间隔向用户发送一次新闻。

  • 向 Argus 注册的指令具有这样的格式：Register Qnum Period
  • Qnum （0 < Qnum ≤ 30000） 是用户的 ID，Period（0 < Period ≤ 3000）是间隔。注册后 Period 秒，结果会第一次到达。
  • 所有的用户都有不同的 Qnum。

桐桐测试了一段时间后，想知道系统前 K 次给谁发送新闻了。如果同一时间发送多个新闻，以 Qnum 的升序排列。

输入：

第一部分是注册指令，每条一行。指令数不超过 1000。此部分以 “ # ” 结束。

第二部分仅一行一个整数 K，K ≤ 10000。

输出：

输出前 K 个新闻发送到的用户的 Qnum，每行一个。

样例：

1
2
3
4
Register 2004 200
Register 2005 300
#
5
1
2
3
4
5
2004
2005
2004
2004
2005

代码

思路：每次取时间最小的进行输出，同为时间最小时再按照ID进行排序，故应该使用优先队列进行处理。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include<iostream>
#include<queue>
#include<string>
using namespace std;

struct node {
	int id;
	int offset;//获得新闻的时间
	int next;//下一次获得新闻的时间（排序依据）
	bool operator<(const node &t) const {//重载小于号 实现大于号的功能(自定义优先队列的排序规则)
		if (this->next == t.next) return this->id > t.id;
		return this->next > t.next;
	}
};

priority_queue<node> que;

int main() {
	int n;
	string str;
	//1.初始化设置
	while (cin >> str) {
		if (str == "#") break;
		int id, offset;
		cin >> id >> offset;
		que.push((node){id, offset, offset});
	}
	//2.输出前n个新闻发送到的用户的Qnum
	cin >> n;
	for (int i = 0; i < n; ++i) {
		node temp = que.top();
		que.pop();
		cout << temp.id << endl;//输出
		temp.next += temp.offset;//数据更新
		que.push(temp);
	}
	return 0;
}