算法训练 区间k大数查询

给定一个序列，每次询问序列中第l个数到第r个数中第K大的数是哪个。

第一行包含一个数n，表示序列长度。

第二行包含n个正整数，表示给定的序列。

第三个包含一个正整数m，表示询问个数。

接下来m行，每行三个数l,r,K，表示询问序列从左往右第l个数到第r个数中，从大往小第K大的数是哪个。序列元素从1开始标号。

对于30%的数据，n,m<=100；

对于100%的数据，n,m<=1000；

保证k<=(r-l+1)，序列中的数<=106。

代码如下：

#include<stdio.h>  
int main()  
{  
    int n, m;  
    int a[1000], b[1000];  
    int i, j, h, t, q, cnt;  
    int first, r, K;  
    scanf("%d",&n);   //输入整数n 
    for( i = 0; i < n; i++ ){  
        scanf("%d",&a[i]);   //输入n个整数 
    }  
    scanf("%d",&m);   //输入整数m 
    for( i = 0; i < n; i++ ){  
        b[i] = a[i];  //把n个整数放入数组b 
    }  
    for( j = 0; j < m; j++ ){  
        scanf("%d%d%d",&first,&r,&K);  //输入第一个数到第r个数，从大往小第k大 
       /*冒泡排序法
   只能应用于有序数列*/
   for( i = 0; i < r - first; i++ ){   //第i趟 
            for( h = 0; h < r - first - i; h++ ){  //每趟循环n(=r-first)-i次 
                if( a[first-1+h] < a[first+h] ){  //比较相邻两个数大小 
                    t = a[first-1+h];  
                    a[first-1+h] = a[first+h];  
                    a[first+h] = t;   //降序排列，从大到小 
                }  
            }  
        }  
        printf("%d\n",a[first+K-2]);  //输出第k大的数 
        for( q = 0; q < n; q++ ){  
            a[q] = b[q];  
        }  
    }  
    return 0;  
}   

关于冒泡排序法：