蓝桥杯 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)，序列中的数<=10 $^6 </annotation> </semantics> </math>$

题解

我们尝试着用动态数组 vector存储数据，如名字所言，它是一个可变化大小的数组，并自带一系列方法
头文件为 #include<vector>
声明为 vector<typename> v
插入数据为v.push_back(elements)
取出数据同普通数组 v[K]
想了解更多请移步官方文档
另外用到了#include<algorithm>下的 sort(start,end,cmp)排序函数，排序[satrt,end) 全部元素，默认是升序排列，当需要定义其他排列规则，可将 cmp 重写
另外比较麻烦的地方是位置的确定，即题干描述的位置和我们数组的位置的映射关系，由于题干是从 1 开始，而我们数组是从 0 开始，所以排序和输出要格外小心

#include<iostream>
#include<algorithm>
#include<vector> //vector
using namespace std;
bool cmp(int a,int b){
	return a>b;
}
int main(){
	int n;
	int m;
	int tmp;
	cin>>n;
	vector<int> v;
	for(int i=0;i<n;i++){ 
		cin>>tmp;
		v.push_back(tmp);
	} 
	cin>>m;
	int start;
	int end;
	int k;
	while(m--){
		cin>>start>>end>>k;
		vector<int> ans(v);  // 复制动态数组v 
		sort(ans.begin()+start-1,ans.begin()+end,cmp);  // 从start-1，到end-1排序 
		cout<<ans[start-1+k-1]<<endl;
	}
	return 0;
}

查看题解目录