uva 1203 Argus

点击打开链接uva 1203

思路: 优先队列
分析:
1 题目要求前k个事件的编号，我们利用优先队列来维护即可
2 优先队列保存的是一个struct，因此我们需要重载<

代码:

#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int MAXN = 20;

struct Node{
    int numId;
    int period;
    int time;
    // 重载<
    bool operator<(const Node& s)const{
        return (time > s.time || (time == s.time && numId > s.numId));     
    }
};
priority_queue<Node>q;
char str[MAXN];
int k;

int main(){
    int x , y;
    while(scanf("%s" , str) && str[0] != '#'){
         scanf("%d%d" , &x , &y);
         q.push((Node){x , y , y});
    }   
    scanf("%d" , &k);
    while(k--){
         Node tmp = q.top();
         q.pop();
         printf("%d\n" , tmp.numId);
         q.push((Node){tmp.numId , tmp.period , tmp.time+tmp.period});
    }
    return 0;
}