蓝桥杯ALGO-1区间k大数查询

问题描述：

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

输入格式：

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

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

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

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

输出格式

总共输出m行，每行一个数，表示询问的答案。

样例输入：

5 1 2 3 4 5 2 1 5 2 2 3 2

样例输出：

4 2

数据规模与约定：

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

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

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

通过代码：

#include <iostream> #include <algorithm> using namespace std; bool cmp(int a, int b) { return a > b; } int main() { int n; cin >> n; int num[n]; for(int i = 0; i < n; i++) { cin >> num[i]; //cout << num[i]; } //cout << endl; int m; cin >> m; while(m--) { int l,r,k; cin >> l >> r >> k; l--; //将从1开始的序列标号转换为从0开始 r--; k--; //cout << l << " " << r << " " << k << endl; int copy[r - l + 1]; //获得目标子序列 //cout << "copy数组:"; //cout << "num数组:"; for(int i = l; i <= r; i++) { copy[i - l] = num[i]; //cout << copy[i - 1] << " "; //cout << num[i] << " "; //cout << i << " "; } //cout << endl; sort(copy, copy + r - l + 1, cmp); //对目标子序列进行排序 //cout << "排序后的copy数组:"; //for(int i = 0; i < r - l + 1; i++) //{ // cout << copy[i] << " "; //} //cout << endl; cout << copy[k] << endl; } return 0; }