`
阿尔萨斯
  • 浏览: 4109144 次
社区版块
存档分类
最新评论

uva 1203 - Argus(优先队列)

 
阅读更多

题目链接:uva 1203 - Argus

题目大意:一个成为Argus的系统,支持一个Register命令

Register Q_num Period

该命令为一个祖册出发器,每Period产生一次Q_num的时间。要求模拟k个事件,如果多个事件同时发生,现处理Q_num小的。

解题思路:用优先队列维护即可,队列中按照时间小的优先,时间相同的比较Q_num,每次处理完一个时间,对应的将时间的时间加上period后放回队列中,表示下一次出发器生成的时间。

#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>

using namespace std;

struct item {
    int num, period, ti;
    bool operator < (const item& a) const {
        return ti > a.ti || (ti == a.ti && num > a.num);
    }
};

int main () {
    priority_queue<item> pri_que;
    char str[105];

    while (scanf("%s", str) == 1 && str[0] != '#') {
        item u;
        scanf("%d%d", &u.num, &u.period);
        u.ti = u.period;;
        pri_que.push(u);
    }

    int Q;
    scanf("%d", &Q);
    for (int i = 0; i < Q; i++) {
        item u = pri_que.top();
        pri_que.pop();

        printf("%d\n", u.num);
        u.ti += u.period;
        pri_que.push(u);
    }
    return 0;
}
分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics