首页 > 专题系列 > Java解POJ > POJ 3078 Q [解题报告] Java
2013
11-12

POJ 3078 Q [解题报告] Java

Q

问题描述 :

You’ve got a queue. And you just got to mess with it.

Given a queue of items and a series of queue operations, return the resulting queue.

Queue operations are defined as follows:

starting-position to requested-position

meaning one wants the item at the starting position to be moved to the requested position. So if the queue of items were:

Item1 Item2 Item3 Item4 Item5

(Item1 being in position 1, Item2 in position 2, etc.)

after applying the queue operation:

5 to 2

the resulting queue would be:

Item1 Item5 Item2 Item3 Item4

as Item5 (the item in position 5) was moved to position 2. Multiple queue operations are applied at the same time, however; e.g., given the queue of items:

Item1 Item2 Item3 Item4 Item5 Item6 Item7 Item8

If the following queue operations were applied:

2 to 6; 6 to 3; 4 to 5; 5 to 2; 7 to 4; 8 to 1

then the resulting queue would be:

Item8 Item5 Item6 Item7 Item4 Item2 Item1 Item3

As you can see, the queue operations are strictly enforced, with other items (not involved in queue operations) maintaining their order and moving to vacant positions in the queue. Note that no two queue operations will have the same starting-position or same requested-position defined.

输入:

Input to this problem will begin with a line containing a single integer x indicating the number of datasets. Each data set consists of three components:
  1. Start line – A single line, “m n” (1 <= m, n <= 20) where m indicates the number of items in the queue and n indicates the number of queue operations.
  2. Queue items – A line of short (between 1 and 8 characters) alphanumeric names for the items in the queue. Names are unique for a given data set and contain no whitespace.
  3. Queue operations – n lines of queue operations in the format “starting-position requested-position”.

输出:

For each dataset, output the queue after the queue operations have been applied. Print the elements of the queue on a single line, starting from the first and ending with the last, with a single space separating each item.

样例输入:

3
5 1
alpha beta gamma delta epsilon
5 2
8 6
a b c d e f g h
2 6
6 3
4 5
5 2
7 4
8 1
3 2
foo bar baz
3 1
1 3

样例输出:

alpha epsilon beta gamma delta
h e f g d b a c
baz bar foo

解题代码:

方法一:
import java.math.BigInteger;
import java.util.*;

public class Main
{
    static String name[] = new String[20];
    static int pos[] = new int[20];
    public static void main(String args[])
    {
       Scanner cin = new Scanner( System.in );
       int t, n, m, a, b;
       t = cin.nextInt();
       while( t-- != 0 ) {
    	 n = cin.nextInt();
    	 m = cin.nextInt();
    	 for( int i=0; i< n; i++ ) {
    	   name[i] = cin.next();
    	   pos[i] = i;
    	 }
    	 boolean sign[] = new boolean[20];
    	 boolean flag[] = new boolean[20];
    	 while( m-- != 0 ) {
    	   a = cin.nextInt();
    	   b = cin.nextInt();
    	   a--;
    	   b--;
    	   pos[b] = a;
    	   sign[a] = true;
    	   flag[b] = true;
    	 }
    	 int j=0;
    	 for( int i=0; i< n; i++ ){
    	   if( flag[i])
    	     System.out.print( name[pos[i]] );
    	   else {
    	     while( sign[j] )
    	       j++;
    	   System.out.print( name[j] );
    	       j++;
    	}
    	if( i< n-1 )
    	   System.out.print( " " );
    	else
    	   System.out.print( "\n" );
     }
   }
   return;
  }
}


方法二:
//* @author: SmilingWang
import java.util.*;

import java.io.*;
public class Main {
  public static void main(String[] args){
   Scanner in = new Scanner(System.in);
   int c = in.nextInt();
   String buf = "";
   for(int i = 0; i < c; i++){
	int m, n;
	m = in.nextInt();
	n = in.nextInt();
	LinkedList< String> q = new LinkedList< String>();
	LinkedList< String> arr = new LinkedList< String>();
	LinkedList< Integer> tArr1 = new LinkedList< Integer>();
	LinkedList< Integer> tArr2 = new LinkedList< Integer>();
	for(int j = 0; j < m; j++){
		String temp = in.next();
		arr.add(temp);
		q.add(temp);
	}
	for(int j = 0; j < n; j++){
         int si = in.nextInt();
	  int ti = in.nextInt();
	  q.set(ti-1, arr.get(si-1));
	  tArr1.add(si-1);
	  tArr2.add(ti-1);
	}
	for(int j1 = 0, j2 = 0; j1 < m && j2 < m; j1++){
	  if(tArr1.contains(j1)){
		continue;
	  }
	String tm = arr.get(j1);
	for(; j2 < m; j2++){
	  if(!tArr2.contains(j2)){
		break;
	}
    }
    q.set(j2, tm);
    j2++;
  }
  Iterator iter = q.iterator();
  while(iter.hasNext()){
	buf += (iter.next() + " ");
  }
  buf += "\n";
 }
 System.out.println(buf);
 }
}

  1. I go through some of your put up and I uncovered a good deal of expertise from it. Many thanks for posting this sort of exciting posts

  2. 不考虑最后将结果排序的话,快排的时间复杂度是O(N) ,而堆排的是O(N*logK),这样比较看,快排快

  3. “再把所有不和该节点相邻的节点着相同的颜色”,程序中没有进行不和该节点相邻的其他节点是否相邻进行判断。再说求出来的也不一样是颜色数最少的