蓝桥杯基础算法训练区间k大数查询（模拟+排序）

小咪咪 2022-03-21 14:41 187阅读 0赞

**问题描述**

**给定一个序列，每次询问序列中第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>
    #include<cstring>
    #include<string>
    #include<map>
    #include<set>
    #include<queue>
    #include<stack>
    #include<cmath>
    #include<cstdio>
    using namespace std;
    
    int main()
    {
    	int a[1000+10],b[1000+10];
    	int n,m,j,k,i,T,x,y;
    	cin>>n;
    	
    	for (i=1;i<=n;i++)
    	cin>>a[i];
    	
    	cin>>m;
    	while (m--)
    	{
    		cin>>x>>y>>k;
    		for (i=x;i<=y;i++)
    		b[i] = a[i];
    		
    		for (i=x;i<=y;i++)
    		{
    			for (j=i+1;j<=y;j++)
    			{
    				if (b[i]<=b[j])
    				swap(b[i],b[j]);
    			}
    		}
    		/*for (i=x;i<=y;i++) cout<<b[i]<<" ";
    		cout<<endl;*/
    		cout<<b[x+k-1]<<endl;
    	}
    	
    	return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，187人围观）

还没有评论，来说两句吧...

相关阅读

相关蓝桥杯算法训练区间k大数查询（排序、查找）

算法训练区间k大数查询时间限制：1.0s 内存限制：256.0MB 问题描述给定一个序列，每次询问序列中第l个数到第r个数中第K大的数是哪个。输入格式第一行

忘是亡心i/ 2024年02月17日 20:43/ 0 赞/ 55 阅读

相关【蓝桥杯】ALGO-1 区间k大数查询排序查找

ALGO-1 区间k大数查询资源限制时间限制：1.0s 内存限制：256.0MB 问题描述给定一个序列，每次询问序列中第l个数到第r个数中第K大的数是哪

末蓝、/ 2022年12月03日 09:14/ 0 赞/ 159 阅读

相关【蓝桥杯】蓝桥杯入门训练+蓝桥杯基础训练

BEGIN-1 A+B问题资源限制时间限制：1.0s 内存限制：256.0MB 问题描述输入A、B，输出A+B。输入格式输入的第一行包括两个

野性酷女/ 2022年12月03日 01:59/ 0 赞/ 458 阅读

相关算法训练区间k大数查询

> 问题描述 > 给定一个序列，每次询问序列中第l个数到第r个数中第K大的数是哪个。 > 输入格式 > 第一行包含一个数n，表示序列长度。 > 第二行包含n个正

傷城~/ 2022年09月28日 13:07/ 0 赞/ 163 阅读

相关蓝桥杯 - 区间k大数查询

给定一串数字，求固定区间的第N大数。因为区间是固定的，是不可以预处理的，所以每有一个区间就拿出这些数字排序，然后输出第N大的数即可 `memcpy(b, a+l, s

以你之姓@/ 2022年06月03日 10:53/ 0 赞/ 186 阅读

相关蓝桥杯 - 区间k大数查询

根据输入的左右区间，放入一个数组，然后进行排序，左位置加上第几位减去1就是这个数字所在的位置 include<cstdio> include<algorith

太过爱你忘了你带给我的痛/ 2022年06月01日 02:35/ 0 赞/ 218 阅读

相关蓝桥杯基础算法训练区间k大数查询（模拟+排序）

问题描述给定一个序列，每次询问序列中第l个数到第r个数中第K大的数是哪个。输入格式第一行包含一个数n，表示序列长度。第二行包含n个正整数，表示给定的序列。第

小咪咪/ 2022年03月21日 14:41/ 0 赞/ 188 阅读

相关蓝桥杯基础算法训练 P0505 （模拟）

　一个整数n的阶乘可以写成n!，它表示从1到n这n个整数的乘积。阶乘的增长速度非常快，例如，13！就已经比较大了，已经无法存放在一个整型变量中；而35！就更大了，它已经无法存放

待我称王封你为后i/ 2022年03月21日 13:14/ 0 赞/ 261 阅读

相关蓝桥杯算法训练（一）区间k大数查询 C语言

区间k大数查询 C语言问题描述给定一个序列，每次询问序列中第l个数到第r个数中第K大的数是哪个。输入格式第一行包含一个数n，表示序列长度。第二行包含n个

小灰灰/ 2022年03月21日 11:25/ 0 赞/ 291 阅读

相关算法训练区间k大数查询(水题)

问题描述给定一个序列，每次询问序列中第l个数到第r个数中第K大的数是哪个。输入格式第一行包含一个数n，表示序列长度。第二行包含n个正整数，表示给定的序列。第

清疚/ 2022年03月07日 21:30/ 0 赞/ 589 阅读