hdu1873（看病要排队）循环队列害死我了

点击打开杭电1873

Problem Description

Input

Output

Sample Input

7
IN 1 1
IN 1 2
OUT 1
OUT 2
IN 2 1
OUT 2
OUT 1
2
IN 1 1
OUT 1

Sample Output

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;
				}
			}
		}
		
	}
}

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;i<n;i++){
				s=sc.next();
				if(s.charAt(0)=='I'){
					count++;
					num=sc.nextInt();
					priority=sc.nextInt();
					Personl p=new Personl(count,priority);
					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 Personl{
	int priority;
	int count;
	public Personl(int count, int priority) {
		this.count=count;
		this.priority=priority;
	}
}
class CirclingQueue{
	int front;
	int end,n;
	Personl[] personl;
	
	public CirclingQueue(int n){
		front =0;
		end = 0;
		this.n=n;
		personl=new Personl[this.n];
	}
	
	public void add(Personl p){
		personl[end] = p;
		end = (end+1)%n;
	}
	public int isEmpty(){
		return front==end ?
 0 : 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