点击打开杭电 1873
只是经过细心的 0068 的观察。他发现了医院里排队还是有讲究的。0068 所去的医院有三个医生(汗。这么少)同一时候看病。而看病的人病情有轻重,所以不能依据简单的先来先服务的原则。所以医院对每种病情规定了 10 种不同的优先级。级别为 10 的优先权最高,级别为 1 的优先权最低。医生在看病时。则会在他的队伍里面选择一个优先权最高的人进行诊治。假设遇到两个优先权一样的病人的话。则选择最早来排队的病人。 如今就请你帮助医院模拟这个看病过程。
每组数据第一行有一个正整数 N(0 接下来有 N 行分别表示发生的事件。 一共同拥有两种事件: 1:"IN A B", 表示有一个拥有优先级 B 的病人要求医生 A 诊治。(0 2:"OUT A", 表示医生 A 进行了一次诊治,诊治完成后,病人出院。(0
假设该事件时无病人须要诊治。则输出 "EMPTY"。 诊治人的编号 ID 的定义为:在一组測试中,"IN A B" 事件发生第 K 次时,进来的病人 ID 即为 K。从 1 開始编号。
- 7
- IN 1 1
- IN 1 2
- OUT 1
- OUT 2
- IN 2 1
- OUT 2
- OUT 1
- 2
- IN 1 1
- OUT 1
- 2
- EMPTY
- 3
- 1
- 1
思路:题意已经非常清楚了,能够用队列做这题。
因为初学队列,不是了解非常深,这题或许也是他们所说的优先队列。
依据题目要求,能够申请三个队列,分别进行操作。而对每一个队列又要考虑优先级,所以在出队列时。能够先对队列中的数据进行一次优先级排序。
仅仅是这里不知道为什么用优先队列就是死都 a 只是去,用普通队列就一次 ac 了。真的非常无语!!
!!
!
!(后面有提供几组有帮助的測试数据)
注:1、要求输出的不是优先级,别看错了哦,而是第几个进来的人的序列号
2、还要对优先级进行排序,别犯错误:找到别当前输出的人的优先级高的,然后进行交换。这是错误的。
普通队列(能 ac):
- import java.util.Scanner;
- public class P1873_2 {
- public static void main(String[] args) {
- Scanner sc = new Scanner(System. in );
- String s;
- int priority,
- num,
- count;
- PersonlQueue[] loopQueue = new PersonlQueue[4]; //申请三个队列,这里的0不用
- while (sc.hasNext()) {
- int n = sc.nextInt();
- count = 0;
- for (int i = 1; i < 4; i++) {
- loopQueue[i] = new PersonlQueue();
- }
- for (int i = 0; i < n; i++) {
- s = sc.next();
- if (s.charAt(0) == 'I') { //若是IN则直接入队就可以
- count++;
- num = sc.nextInt();
- priority = sc.nextInt();
- PPersonl p = new PPersonl(count, priority); //这是一个PPersonl类,就是存放每一个人的优先级,还有就是第几个输入的(这也是为什么要单独建一个类的原因)
- loopQueue[num].add(p); //入队
- } else { //出队
- num = sc.nextInt();
- int a = loopQueue[num].pop();
- if (a == 0) {
- System.out.println("EMPTY");
- } else {
- System.out.println(a);
- }
- }
- }
- }
- }
- }
- class PPersonl {
- int priority; //优先级
- int count; //人的序列号(第几个人) ,也就是要求要输出的数
- public PPersonl(int count, int priority) {
- this.count = count;
- this.priority = priority;
- }
- }
- class PersonlQueue {
- int end;
- final int FRONT = 0;
- PPersonl[] personl;
- public PersonlQueue() {
- end = 0;
- personl = new PPersonl[10000];
- }
- public void add(PPersonl p) { //入队
- personl[end] = p;
- end++;
- }
- public int isEmpty() { //推断是否为空,在此题并没有什么卵用
- if (end <= 0) {
- return 0;
- }
- return 1;
- }
- public int pop() { //出队
- if (end <= 0) {
- return 0;
- }
- sort(); //对优先级进行排序
- int p = personl[FRONT].count;
- if (end > 1) { //队首出队,则后面的要补上来
- for (int i = 0; i < end; i++) {
- personl[i] = personl[i + 1];
- }
- }
- end--;
- return p;
- }
- private void sort() { //冒泡排序
- for (int i = 0; i < end - 1; i++) {
- for (int j = 0; j < end - i - 1; j++) {
- if (personl[j].priority < personl[j + 1].priority) {
- PPersonl temp = personl[j];
- personl[j] = personl[j + 1];
- personl[j + 1] = temp;
- }
- }
- }
- }
- }
循环队列(wa):
- package xjj;
- import java.util.Scanner;
- public class P1873 {
- public static void main(String[] args) {
- Scanner sc = new Scanner(System. in );
- String s;
- int priority,
- num,
- count;
- CirclingQueue[] loopQueue = new CirclingQueue[4];
- while (sc.hasNext()) {
- int n = sc.nextInt();
- count = 0;
- for (int i = 1; i < 4; i++) {
- loopQueue[i] = new CirclingQueue(n);
- }
- for (int i = 0; i0: 1;
- }
- public int pop() {
- if (isEmpty() == 0) {
- return 0;
- }
- sort();
- int p = personl[front].count;
- front = (front + 1) % n;
- return p;
- }
- private void sort() {
- for (int i = front; i < end - 1; i++) {
- for (int j = front; j < end - i - 1; j++) {
- if (personl[j].priority < personl[j + 1].priority) {
- Personl temp = personl[j];
- personl[j] = personl[j + 1];
- personl[j + 1] = temp;
- }
- }
- }
- }
- }
測试数据:
7 IN 1 10
IN 1 5
IN 1 8
IN 1 4
OUT 1
OUT 1
OUT 1
结果:1 3 2 12 IN 1 10
IN 1 4
IN 1 4
IN 1 5
IN 1 4
IN 1 4
OUT 1
OUT 1
OUT 1
OUT 1
OUT 1
OUT 1
结果:1 4 2 3 5 6
来源: http://www.bubuko.com/infodetail-2118495.html