【优先队列之多路归并】UVALive 3135 Argus

UVALive 3135 Argus

http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=18684

题意

编写一个系统执行一系列Register命令：Register Q_num Period,每个命令执行周期是Period,执行事件Q_num；如果事件同时发生，优先执行Q_num小的。

示例

Sample Input
Register 2004 200
Register 2005 300
#
5
Sample Output
2004
2005
2004
2004
2005

思路

★ 典型多路合并问题，用优先队列维护将要发生的下一个事件，优先队列内容要事先定义优先级，总时间复杂度O（klogn）

参考代码

#include<bits/stdc++.h>
using namespace std;

const int _max = 2e4 + 10;
char s[20];
int n;
struct Item{
 int Q_num,Period,time;
 bool operator < (const Item &a) const{//const必不可少,解释优先级低
   return (time > a.time) || (time == a.time && Q_num > a.Q_num);
 }
};
priority_queue<Item>pq;

int main(){
 #ifndef ONLINE_JUDGE
 freopen("input.txt","r",stdin);
 #endif // ONLINE_JUDGE
 Item item;
 while(scanf("%s",s) == 1 && s[0] != ‘#‘){
    scanf("%d%d",&item.Q_num,&item.Period);
    item.time = item.Period;
    pq.push(item);
 }
 scanf("%d",&n);
 for(int i = 0; i < n; ++ i){
    item = pq.top();          //堆顶
    pq.pop();
    printf("%d\n",item.Q_num);
    item.time += item.Period;//更新下一个事件的时间
    pq.push(item);
 }
 return 0;
}

• 加粗 Ctrl + B
• 斜体 Ctrl + I
• 引用 Ctrl + Q
• 插入链接 Ctrl + L
• 插入代码 Ctrl + K
• 插入图片 Ctrl + G
• 提升标题 Ctrl + H
• 有序列表 Ctrl + O
• 无序列表 Ctrl + U
• 横线 Ctrl + R
• 撤销 Ctrl + Z
• 重做 Ctrl + Y