本文主要是介绍ural 1026. Questions and Answers 查询，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
1026. Questions and Answers
Time limit: 2.0 second
Memory limit: 64 MB
Memory limit: 64 MB
Background
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 integers 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 an integer in a range from 1 to N.
Problem
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.
Input
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 "#".
Output
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).
Sample
| input | output |
|---|---|
5 7 121 123 7 121 ### 4 3 3 2 5 | 121 121 7 123 |
Problem Author: Leonid Volkov
Problem Source: Ural State University Internal Contest October'2000 Junior Session
Problem Source: Ural State University Internal Contest October'2000 Junior Session
import java.io.BufferedReader;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.Arrays;
import java.util.StringTokenizer;public class Main {public static void main(String[] args) {new Task().solve();}
}class Task {InputReader in = new InputReader(System.in) ;PrintWriter out = new PrintWriter(System.out);class Query implements Comparable<Query>{int idx ;int num ;Query(int idx , int num) {this.idx = idx ;this.num = num ; }@Overridepublic int compareTo(Query other) {return Integer.compare(this.num , other.num) ;}}void solve() {int n = in.nextInt() ;int[] cnt = new int[5001] ;Arrays.fill(cnt , 0) ;while(n-- > 0){cnt[in.nextInt()]++ ;}int[] sum = new int[5001] ;sum[0] = 0 ;for(int i = 1 ; i <= 5000 ; i++){sum[i] = sum[i-1] + cnt[i] ;}in.next() ;int k = in.nextInt() ;Query[] query = new Query[k] ;for(int i = 0 ; i < k ; i++){query[i] = new Query(i , in.nextInt()) ;}Arrays.sort(query) ;int idx = 0 ;int[] result = new int[k] ;for(int v = 1 ; v <= 5000 ; v++){if(cnt[v] == 0){continue ; }while(idx < k && sum[v-1] < query[idx].num && query[idx].num <= sum[v]){result[query[idx].idx] = v ;idx++ ;}}Arrays.stream(result).forEach(out::println);out.flush();}}class InputReader { public BufferedReader reader; public StringTokenizer tokenizer; public InputReader(InputStream stream) { reader = new BufferedReader(new InputStreamReader(stream), 32768); tokenizer = new StringTokenizer(""); } private void eat(String s) { tokenizer = new StringTokenizer(s); } public String nextLine() { try { return reader.readLine(); } catch (Exception e) { return null; } } public boolean hasNext() { while (!tokenizer.hasMoreTokens()) { String s = nextLine(); if (s == null) return false; eat(s); } return true; } public String next() { hasNext(); return tokenizer.nextToken(); } public int nextInt() { return Integer.parseInt(next()); } public int[] nextInts(int n){ int[] nums = new int[n] ; for(int i = 0 ; i < n ; i++){ nums[i] = nextInt() ; } return nums ; } public long nextLong() { return Long.parseLong(next()); } public double nextDouble() { return Double.parseDouble(next()); } public BigInteger nextBigInteger() { return new BigInteger(next()); } } 这篇关于ural 1026. Questions and Answers 查询的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
