首页 > 代码库 > POJ 2371 Questions and answers
POJ 2371 Questions and answers
Description
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.
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
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 "#".
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
571211237121###43325
Sample Output
1211217123
题目大意：就是给你一组数，上面是数，下面是第几个数，一个排序就搞定
1 #include<stdio.h> 2 int n,a[999999],b[999999]; 3 void kuaipai(int left,int right) 4 { 5 int i,j,t,temp; 6 if(left>right) 7 return; 8 temp=a[left]; 9 i=left;10 j=right;11 while(i!=j)12 {13 while(a[j]>=temp && i<j)14 j--;15 while(a[i]<=temp && i<j)16 i++;17 if(i<j)18 {19 t=a[i];20 a[i]=a[j];21 a[j]=t;22 }23 }24 a[left]=a[i];25 a[i]=temp;26 kuaipai(left,i-1);27 kuaipai(i+1,right);28 }29 int main()30 {31 while(scanf("%d",&n)!=EOF)32 {33 int i,j;34 for(i=1;i<=n;i++)35 {36 scanf("%d",&a[i]);37 }38 kuaipai(1,n);39 char s[100];40 scanf("%s",s);41 scanf("%d",&n);42 for(i=1;i<=n;i++)43 scanf("%d",&b[i]);44 for(i=1;i<=n;i++)45 printf("%d\n",a[b[i]]);46 47 48 }49 return 0;50 }
POJ 2371 Questions and answers
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。