HDU1873 看病要排队 STL优先队列

2024-03-30 02:58

本文主要是介绍HDU1873 看病要排队 STL优先队列,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目描述

看病要排队这个是地球人都知道的常识。
不过经过细心的0068的观察,他发现了医院里排队还是有讲究的。0068所去的医院有三个医生(汗,这么少)同时看病。而看病的人病情有轻重,所以不能根据简单的先来先服务的原则。所以医院对每种病情规定了10种不同的优先级。级别为10的优先权最高,级别为1的优先权最低。医生在看病时,则会在他的队伍里面选择一个优先权最高的人进行诊治。如果遇到两个优先权一样的病人的话,则选择最早来排队的病人。
现在就请你帮助医院模拟这个看病过程。

简化题目:
三个医生同时看病,病人按照优先级顺序排队,级别为10的优先级最高,为1最低。
现在有若干组入队和出队操作,判断每一次出队操作出队了什么编号的病人(或为空)。

Input

输入数据包含多组测试,请处理到文件结束。
每组数据第一行有一个正整数N(0 < N < 2000)表示发生事件的数目。
接下来有N行分别表示发生的事件。
一共有两种事件:
1:”IN A B”,表示有一个拥有优先级B的病人要求医生A诊治.(1 <= A <= 3,1 <= B <= 10)
2:”OUT A”,表示医生A进行了一次诊治,诊治完毕后,病人出院。(1 <= A <=3)

Output

对于每个”OUT A”事件,请在一行里面输出被诊治人的编号ID。如果该事件时无病人需要诊治,则输出”EMPTY”。
诊治人的编号ID的定义为:在一组测试中,”IN A B”事件发生第K次时,进来的病人ID即为K。从1开始编号。

思路分析

显然队列的出队入队都涉及到了优先级的问题,因此应采用优先队列。
优先队列的使用可以用STL的priority_queue,默认是大数在前。

注意事项

1.注意重载一个<,且重载前要加一个friend。
2.注意每次结束后把队列内剩下的元素都弹出。

代码

比较丑陋,没有用优先队列的数组,分别开了三个优先队列:

#include<iostream>
#include<string>
#include<stdio.h>
#include<queue>
using namespace std;
struct pnt {        //patient 记录每个病人的优先级和入队时间 int imp;int time;friend bool operator < (pnt a,pnt b) {if(a.imp==b.imp)    return a.time>b.time;return a.imp<b.imp;}
};
/*三个优先队列*/
priority_queue<pnt>A;
priority_queue<pnt>B;
priority_queue<pnt>C;
int main() {int n,a,b,k;string in;pnt tmp;while(scanf("%d",&n)==1) {k=1;/*将队列里剩余的元素弹出*/while(!A.empty())   A.pop();while(!B.empty())   B.pop();while(!C.empty())   C.pop();for(int i=1; i<=n; i++) {cin>>in;if(in=="IN") {scanf("%d %d",&a,&b);tmp.time=k++;tmp.imp=b;if(a==1) {A.push(tmp);} else if(a==2) {B.push(tmp);} else {C.push(tmp);}} else {scanf("%d",&a);switch(a) {case 1 : {if(A.empty()) { //队列为空则输出EMPTY puts("EMPTY");} else {        //队列不为空则输出顶上的时间并出队 printf("%d\n",A.top().time);A.pop();}break;}case 2: {if(B.empty()) {puts("EMPTY");} else {printf("%d\n",B.top().time);B.pop();}break;}case 3: {if(C.empty()) {puts("EMPTY");} else {printf("%d\n",C.top().time);C.pop();}break;}}}}}return 0;
}

这篇关于HDU1873 看病要排队 STL优先队列的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/860314

相关文章

Java的栈与队列实现代码解析

《Java的栈与队列实现代码解析》栈是常见的线性数据结构,栈的特点是以先进后出的形式,后进先出,先进后出,分为栈底和栈顶,栈应用于内存的分配,表达式求值,存储临时的数据和方法的调用等,本文给大家介绍J... 目录栈的概念(Stack)栈的实现代码队列(Queue)模拟实现队列(双链表实现)循环队列(循环数组

Redis消息队列实现异步秒杀功能

《Redis消息队列实现异步秒杀功能》在高并发场景下,为了提高秒杀业务的性能,可将部分工作交给Redis处理,并通过异步方式执行,Redis提供了多种数据结构来实现消息队列,总结三种,本文详细介绍Re... 目录1 Redis消息队列1.1 List 结构1.2 Pub/Sub 模式1.3 Stream 结

SpringKafka错误处理(重试机制与死信队列)

《SpringKafka错误处理(重试机制与死信队列)》SpringKafka提供了全面的错误处理机制,通过灵活的重试策略和死信队列处理,下面就来介绍一下,具有一定的参考价值,感兴趣的可以了解一下... 目录引言一、Spring Kafka错误处理基础二、配置重试机制三、死信队列实现四、特定异常的处理策略五

Spring Boot整合消息队列RabbitMQ的实现示例

《SpringBoot整合消息队列RabbitMQ的实现示例》本文主要介绍了SpringBoot整合消息队列RabbitMQ的实现示例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的... 目录RabbitMQ 简介与安装1. RabbitMQ 简介2. RabbitMQ 安装Spring

如何通过Python实现一个消息队列

《如何通过Python实现一个消息队列》这篇文章主要为大家详细介绍了如何通过Python实现一个简单的消息队列,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录如何通过 python 实现消息队列如何把 http 请求放在队列中执行1. 使用 queue.Queue 和 reque

解读Redis秒杀优化方案(阻塞队列+基于Stream流的消息队列)

《解读Redis秒杀优化方案(阻塞队列+基于Stream流的消息队列)》该文章介绍了使用Redis的阻塞队列和Stream流的消息队列来优化秒杀系统的方案,通过将秒杀流程拆分为两条流水线,使用Redi... 目录Redis秒杀优化方案(阻塞队列+Stream流的消息队列)什么是消息队列?消费者组的工作方式每

Redis延迟队列的实现示例

《Redis延迟队列的实现示例》Redis延迟队列是一种使用Redis实现的消息队列,本文主要介绍了Redis延迟队列的实现示例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习... 目录一、什么是 Redis 延迟队列二、实现原理三、Java 代码示例四、注意事项五、使用 Redi

hdu1180(广搜+优先队列)

此题要求最少到达目标点T的最短时间,所以我选择了广度优先搜索,并且要用到优先队列。 另外此题注意点较多,比如说可以在某个点停留,我wa了好多两次,就是因为忽略了这一点,然后参考了大神的思想,然后经过反复修改才AC的 这是我的代码 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<

poj 3190 优先队列+贪心

题意: 有n头牛,分别给他们挤奶的时间。 然后每头牛挤奶的时候都要在一个stall里面,并且每个stall每次只能占用一头牛。 问最少需要多少个stall,并输出每头牛所在的stall。 e.g 样例: INPUT: 51 102 43 65 84 7 OUTPUT: 412324 HINT: Explanation of the s

poj 2431 poj 3253 优先队列的运用

poj 2431: 题意: 一条路起点为0, 终点为l。 卡车初始时在0点,并且有p升油,假设油箱无限大。 给n个加油站,每个加油站距离终点 l 距离为 x[i],可以加的油量为fuel[i]。 问最少加几次油可以到达终点,若不能到达,输出-1。 解析: 《挑战程序设计竞赛》: “在卡车开往终点的途中,只有在加油站才可以加油。但是,如果认为“在到达加油站i时,就获得了一