本文主要是介绍蓝桥杯【算法训练】区间K大数查询，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

资源限制

时间限制：1.0s   内存限制：256.0MB

问题描述

给定一个序列，每次询问序列中第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。

解题思路

先将序列中区间为[l,r]的数取出来放到另外一个数组b中，然后对b进行降序排列，再输出其中第K个数即为该区间的第K大数字。这里注意，一定要先取出区间内的数然后再排序，而不是先操作原序列中[l,r]中的数字对其进行排序，否则将改变原序列的相对位置而导致出错！

代码

用到了动态数组vector以及sort排序函数，不了解它们用法的小伙伴看这两篇文章

C++动态数组容器vector                                      

C++常用的sort排序函数

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
bool cmp(int a,int b){
	return b<a;
}
int main(){
	int i,j,n;
	int l,r,k,m;
	vector<int>s;
	int a[1001],b[1001];
	cin>>n; 
	for(i=0;i<n;i++)
	   cin>>a[i];
	cin>>m;
	while(m--){
		cin>>l>>r>>k;
		for(i=l-1,j=0;i<r;i++,j++){
			b[j]=a[i];//先取出区间内的值放入数组b 
		}
		sort(b+l,b+r-l+1,cmp);//对区间[l,r]内的数进行降序排列 
		s.push_back(b[k-1]);//因为K为序列号，所以K-1才是该区间内的第K大数，将其加入到动态数组S中 
	}
	//依次输出结果 
	for(i=0;i<s.size();i++)
	   cout<<s[i]<<endl;
	return 0;
}

评测结果

 如果有收获，别忘记带个赞哦！

这篇关于蓝桥杯【算法训练】区间K大数查询的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！