首页 > 代码库 > UVA1203Argus(优先队列)

UVA1203Argus(优先队列)

题目:UVA1203Argus(优先队列)


题目大意:给你多个项目,每个项目有它发生的周期和对应的Q_num值。现在要求给出前K个项目,时间优先,同一时刻发生的先输出Q_num值小的。


解题思路:先将这几个项目排下顺序,一开始这些项目的发生时间就是周期,按照时间优先和同一时刻的Q_num优先的原则将这个项目在priority_queue排下序,然后输出前K个。当输出某个项目的时候,同时也将这个项目的下个项目开始的时间更新在放入队列中。这样重复K次就可以了。


代码:

#include <cstdio>
#include <queue>

using namespace std;

const int N = 10;
const int maxn = 1005;

struct Item {

	int num, period, time;
	bool operator < (const Item &a) const {
		
		return time > a.time || (time == a.time && num > a.num);
	}
}item[maxn];

priority_queue <Item> q;

int main () {
		
	char str[N];
	Item tmp;
	int K;

	while (scanf ("%s", str) == 1 && str[0] != '#') {

		scanf ("%d%d", &tmp.num, &tmp.period);
		tmp.time = tmp.period;
		q.push (tmp);
	}
	
	scanf ("%d", &K);
	
	while (K--) {
		
		tmp = q.top();
		q.pop();
		printf ("%d\n", tmp.num);
		tmp.time += tmp.period;
		q.push (tmp);
	}
	return 0;
}


UVA1203Argus(优先队列)