首页 > 专题系列 > Java解POJ > POJ 1281 MANAGER [解题报告] Java
2013
11-09

POJ 1281 MANAGER [解题报告] Java

MANAGER

问题描述 :

One of the programming paradigm in parallel processing is the producer/consumer paradigm that can be implemented using a system with a “manager” process and several “client” processes. The clients can be producers, consumers, etc. The manager keeps a trace of client processes. Each process is identified by its cost that is a strictly positive integer in the range 1 .. 10000. The number of processes with the same cost cannot exceed 10000. The queue is managed according to three types of requests, as follows:
  • a x – add to the queue the process with the cost x;
  • r – remove a process, if possible, from the queue according to the current manager policy;
  • p i – enforce the policy i of the manager, where i is 1 or 2. The default manager policy is 1
  • e – ends the list of requests.

There are two manager policies:

  • 1 – remove the minimum cost process
  • 2 – remove the maximum cost process

The manager will print the cost of a removed process only if the ordinal number of the removed process is in the removal list.

Your job is to write a program that simulates the manager process.

输入:

The input is from the standard input. Each data set in the input has the following format:
  • the maximum cost of the processes
  • the length of the removal list
  • the removal list – the list of ordinal numbers of the removed processes that will be displayed; for example 1 4 means that the cost of the first and fourth removed processes will be displayed
  • the list of requests each on a separate line.

Each data set ends with an e request. The data sets are separated by empty lines.

输出:

The program prints on standard output the cost of each process that is removed, provided that the ordinal number of the remove request is in the list and the queue is not empty at that moment. If the queue is empty the program prints -1. The results are printed on separate lines. An empty line separates the results of different data sets.

An example is given in the following:

样例输入:

5
2
1 3
a 2
a 3
r
a 4
p 2
r
a 5
r
e

样例输出:

2
5

解题代码:

import java.io.PrintWriter; 
import java.io.PrintWriter; 
import java.util.Collections; 
import java.util.PriorityQueue;
import java.util.Scanner; 

public class Main { 
  Scanner cin = new Scanner(System.in);
  PrintWriter out=new PrintWriter(System.out,true);
  
  public void solve() {
   int maxCost,removeLen; 
   String op; 
   while(cin.hasNext()) {
    maxCost=cin.nextInt();
    removeLen=cin.nextInt(); 
    int [] list=new int[removeLen];
    for(int i=0; i< removeLen; i++) 
     list[i]=cin.nextInt();
 
  PriorityQueue< Integer> minQ=new PriorityQueue< Integer>();
  PriorityQueue< Integer> maxQ=new PriorityQueue< Integer>(1000,Collections.reverseOrder());
  int state=1,cost,step=1,flagRemove=0,temp; op=cin.next();
  while(!op.equals("e")) {
   if(op.equals("a")) {
    cost=cin.nextInt();
    maxQ.add(cost);
    minQ.add(cost);
   } else if(op.equals("r")) {
     if(maxQ.isEmpty()) //empty 
       out.println("-1");
    else //not empty 
    { 
     if(state==1){
      temp=minQ.poll(); 
      maxQ.remove(temp);  
     } else {
      temp=maxQ.poll();
       minQ.remove(temp);   
    } 
  if(flagRemove< removeLen&&step==list[flagRemove]) //show 
 { 
   out.println(temp); 
   flagRemove++; 
  } 
 } step++; 
} else // op==p 
{ 
 state=cin.nextInt();
 } 
op=cin.next();
 } 
out.println("");
 } 
out.close();
 }
 
public static void main(String[] args) {
    Main m = new Main(); 
    m.solve();
  }
 }

  1. Good task for the group. Hold it up for every yeara??s winner. This is a excellent oppotunity for a lot more enhancement. Indeed, obtaining far better and much better is constantly the crucial. Just like my pal suggests on the truth about ab muscles, he just keeps obtaining much better.