2013
11-11

# POJ 2371 Questions and answers [解题报告] Java

The database of the Pentagon contains a top-secret information. We don’t know what the information is — you know, it’s top-secret, — but we know the format of its representation. It is extremely simple. We don’t know why, but all the data is coded by the natural numbers from 1 up to 5000. The size of the main base (we’ll denote it be N) is rather big — it may contain up to 100 000 those numbers. The database is to process quickly every query. The most often query is: “Which element is i-th by its value?”— with i being a natural number in a range from 1 to N.

Your program is to play a role of a controller of the database. In the other words, it should be able to process quickly queries like this.

The standard input of the problem consists of two parts. At first, a database is written, and then there’s a sequence of queries. The format of database is very simple: in the first line there’s a number N, in the next N lines there are numbers of the database one in each line in an arbitrary order. A sequence of queries is written simply as well: in the first line of the sequence a number of queries K (1 <= K <= 100) is written, and in the next K lines there are queries one in each line. The query "Which element is i-th by its value?" is coded by the number i. A database is separated from a sequence of queries by the string of three symbols "#".

The output should consist of K lines. In each line there should be an answer to the corresponding query. The answer to the query “i” is an element from the database, which is i-th by its value (in the order from the least up to the greatest element).

5
7
121
123
7
121
###
4
3
3
2
5

121
121
7
123

import java.util.Arrays;
import java.util.Scanner;
public class Main {

public static void quickSort(int[] data, int s, int t) {
int i = s+1;
int j = t;
int x = data[s];
while (i <= j) {
while (i <= j && data[j] >= x)
--j;
while (i <= j && x >= data[i])
++i;
if (i <= j) {
data[i] = data[j] + ((data[j] = data[i]) & 0);
i++;
j--;
}
}

if (j != s) {
data[s] = data[j];
data[j] = x;
}
if (s < j - 1)
quickSort(data, s, j - 1);
if (j + 1 < t)
quickSort(data, j + 1, t);
}

public static void main(String[] args) {

Scanner sc = new Scanner(System.in);
int sum = sc.nextInt();
int[] database = new int[sum];
for (int i = 0; i < sum; ++i) {
database[i] = sc.nextInt();
}
// Arrays.sort(database);
quickSort(database, 0, database.length-1);
sc.nextLine();
sc.nextLine();
int queryCount = sc.nextInt();
for (int i = 0; i < queryCount; ++i) {
int queryNum = sc.nextInt();
System.out.println(database[queryNum - 1]);
}
//		for(int i = 0 ; i < database.length ;++i)
//			System.out.print(database[i]+" ");
}

}

1. 5.1处，反了；“上一个操作符的优先级比操作符ch的优先级大，或栈是空的就入栈。”如代码所述，应为“上一个操作符的优先级比操作符ch的优先级小，或栈是空的就入栈。”