首页 > 专题系列 > Java解POJ > POJ 2371 Questions and answers [解题报告] Java
2013
11-11

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

Questions and answers

问题描述 :

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的优先级小,或栈是空的就入栈。”