当前位置: 首页 > 工具软件 > Argus > 使用案例 >

POJ 2051 Argus(优先队列)

宋建柏
2023-12-01

4.1基础数据结构

1、优先队列

其实我不怎么看得懂这本书里写的题意所以就还是大概写写吧

题意:
每行输入一条循环活动指令的注册 格式大致为:Register [活动编号] [活动时间间隔], 以"#"号结尾 ,完成注册以后便会按照时间先后执行, 如第一行为例子 , 2004代表编号 , 200代表活动执行间隔.
最后一行表示前n个被执行的活动

输入:
Register 2004 200
Register 2005 300
#
5
输出:
2004
2005
2004
2004
2005

1、一般这种有id或者对应值的用struct比较多

2、运算符定义(//默认的优先队列是最大堆,使用我们定义的比较方法后反转为最小堆。)

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <queue>
using namespace std;
#define int long long
const int maxn=100000;
char s[20];
int k;
int read()
{ 
   int x=0,fl=1; char ch=getchar();
   while (ch<'0' || ch>'9') {  if (ch=='-')  fl=-1; ch=getchar();}
   while (ch>='0' && ch<='9') {  x=x*10+(ch-'0'); ch=getchar(); }
   return x*fl;
}
struct Item{
	int q,p,t;
	bool operator<(const Item& a) const{
	if (t!=a.t) return t>a.t;
	return  q >a.q;
	} 
}b,r;
priority_queue<Item> pq;
signed main(){
   while (true){
     scanf("%s",s);
	 if (s[0]=='#') break; else { b.q=read(); b.p=read(); b.t=b.p; pq.push(b);}   	
   } 
   k=read();
   while (k--){
   	  r=pq.top();
   	  pq.pop();
	  cout<<r.q<<endl;
	  r.t+=r.p;pq.push(r); 
   }
   return 0;
} 

 类似资料: