题目大意,给定一个整数序列a[N],询问区间ai到aj之间第k大的数是多少。共m次询问,对每次询问输出结果。
此题可用伴随数组处理。具体做法是在输入的时候用一个数组保存每个数的序号,我们称这个数组为伴随数组,输入完成后,对数组进行排序,但对应的序号不变(用结构体将该数及其序号绑定,然后对结构体排序)。上面这个过程可以看成是预处理,接下来,对于每个询问i,j,k,只需对排序后的数组扫描一次即可,碰到序号在i到j之间的就--k,直到k为0,此时对应的数即为所求。
View Code
1 #include <stdio.h> 2 #define N 100000 3 struct node 4 { 5 int x,id; 6 }node[N]; 7 int cmp(void const*a,void const*b) 8 { 9 return ((struct node*)a)->x-((struct node*)b)->x; 10 } 11 int main() 12 { 13 int i,j,n,m,a,b,k; 14 while(~scanf("%d%d",&n,&m)) 15 { 16 for(i=0;i<n;i++) 17 { 18 scanf("%d",&node[i].x); 19 node[i].id=i; 20 } 21 qsort(node,n,sizeof(node[0]),cmp); 22 for(i=0;i<m;i++) 23 { 24 scanf("%d%d%d",&a,&b,&k); 25 a--,b--; 26 for(j=0;j<n;j++) 27 { 28 if(node[j].id>=a&&node[j].id<=b) k--; 29 if(!k) 30 { 31 printf("%d\n",node[j].x); 32 break; 33 } 34 } 35 } 36 } 37 return 0; 38 }