首页 > > 程序设计 > C/C++ >

算法训练区间k大数查询

2019-02-20 00:43:48来源：博客园阅读 ()

分享一道蓝桥杯的题算法训练区间k大数查询网址 http://lx.lanqiao.cn/problem.page?gpid=T11

算法训练区间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⁶。

思路就是查询的节点放进新的数组里，对它进行排序，然后输出第K大就ok了。

#include<iostream>

#include<algorithm>

#include<cstring>

using namespace std;

int arr[1050],mem[1050];

int main(){

int n,l,r,k;

cin>>n;

for(int i=1;i<=n;i++)cin>>arr[i];

int m;

cin>>m;

while(m--){

cin>>l>>r>>k;

int n=(r-l+1); //统计出查询的范围

memcpy(mem,arr+l,n*sizeof(int)); 复制到新的数组里，mem数组是接受复制数组，arr就是原数据所在的数组了。

sort(mem,mem+n); //排序

cout<<mem[n-k]<<endl;　　

}

return 0;

}

原文链接:https://www.cnblogs.com/suifengfengyi/p/10401439.html
如有疑问请与原作者联系

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有

上一篇：【HDU - 1429】胜利大逃亡(续) （高级搜索）【状态压缩+BFS】

下一篇：题解-洛谷P1020P导弹拦截（求单调序列长度的优化）

C++ rand函数 2020-06-10
OpenCV开发笔记（五十九）：红胖子8分钟带你深入了解分水岭 2020-05-24
类欧几里得算法 2020-05-16
算法笔记刷题6 ( PAT 1003我要通过 ) 2020-05-08
无法正确通过算法题目都是哪些原因造成的？ 2020-04-05

IDC资讯：主机资讯注册资讯托管资讯 vps资讯网站建设

网站运营：建站经验策划盈利搜索优化网站推广免费资源

网站联盟：联盟新闻联盟介绍联盟点评网赚技巧

行业资讯：搜索引擎网络游戏电子商务广告传媒

网络编程： Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它

服务器技术： Web服务器 Ftp服务器 Mail服务器 Dns服务器安全防护

软件技巧：其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷

网页制作： FrontPages Dreamweaver Javascript css photoshop fireworks Flash

程序设计： Java技术 C/C++ VB delphi

网络知识：网络协议网络安全网络管理组网方案 Cisco技术

操作系统： Win2000 WinXP Win2003 Mac OS Linux FreeBSD

热门词条

最新资讯

热门关注

热门标签

算法训练 区间k大数查询

算法训练区间k大数查询