第K个数
Description
给你一个整数序列和若干个问题,问题是这个序列的第i个元素到第j个元素的片断中的第k大数是什么?比如说给你的序列为(1, 5, 2, 6, 3, 7, 4),问题是(2,5,3),则从第2个元素到第5个元素为(5,2,6,3),排序以后是(2,3,5,6),则第三个数是5。
输入:
第一行为两个整数n,m(1 <= n <= 100 000, 1 <= m <= 5 000),表示序列的元素个数和问题的个数,第二行为n个正整数的序列,每个整数为一个32位整数,两个数之间有一个空格隔开。以后m行为问题,每个问题由三个整数表示i,j,k,第i个元素到第j个元素的片断中的第k大数是什么?(元素序号从1开始计数,i<=j,1<=k<=j-i+1)
输出:
每行输出对应问题的结果。
Sample Input
7 3
1 5 2 6 3 7 4
2 5 3
4 4 1
1 7 3
Sample Output
5
6
3
#include<iostream>
using namespace std;
typedef struct nodes
{
int value;
int num;
};
nodes node[1000];
void quick_sort(int low,int high)
{
int i,j;
nodes key;
if(low<high)
{
i=low;
j=high;
key=node[low];
while(i<j)
{
while(i<j&&key.value<=node[j].value) j--;
node[i]=node[j];
while(i<j&&key.value>=node[i].value) i++;
node[j]=node[i];
}
node[i]=key;
quick_sort(low,i-1);
quick_sort(i+1,high);
}
}
int main()
{
int n;
cin>>n;
int cases;
cin>>cases;
int i=0;
for(i=0;i<n;i++)
{
cin>>node[i].value;
node[i].num=i+1;
}
quick_sort(0,n-1);
while(cases--)
{
int a,b,c,sum=0;
cin>>a>>b>>c;
for(i=0;i<n;i++)
{
if(a<=node[i].num&&node[i].num<=b)
{
sum++;
if(sum==c)
{
cout<<node[i].value<<endl;
break;
}
}
}
}
return 0;
}
分享到:
相关推荐
c++实现的A*算法求K短路模板,内有注释,根据注释代码很容易理解
文演整理版 2008-3-23 数论: 1007 Numerical Summation of a Series 简单题,还是蛮有意思的 1045 HangOver 简单题 1049 I Think I Need a Houseboat 简单题 1028 Flip and Shift 简单题,可以DP/BFS/……,...
int n, i, j, k, x, y, z, s = 0, m; scanf("%d", &n); for (i = 2; i ; i++) { for (j = 1; j ; j++) { if (n >= 3) { for (k = 1; k ; k++) { if (n >= 4) { for (x = 1; x ; x++) { if (n >= 5) ...
红黑树的C语言实现,附加了顺序统计域,思想源自《算法导论》第三版ch13伪代码,基于的具体问题为:学校举办了一个在线ACM比赛,快速实现榜单的插入、删除、第k小查询
实现:利用C++实现各种数据结构和经典算法 KMP算法: 二叉树的创建,展示,以及、三种遍历方法(先根,后根,中跟)的递归非递归实现:/Cplus_algorithm/binTree.cpp 值得留意的题目:树相关。具体有: 参考: [394....
安格斯快船多边形和线剪裁和偏移库归因这个库中的代码是 Bala Vatti 裁剪算法的扩展:“多边形裁剪的通用解决方案” ACM 通讯,第 35 卷,第 7 期(1992 年 7 月)第 56-63 页。 计算机图形学和几何建模:实现和算法...
本书旨在探讨如何优化算法效率,详细阐述了经典算法和特殊算法的实现、应用技巧和复杂度验证过程,内容由浅入深,能帮助读者快速掌握复杂度适当、正确率高的高效编程方法以及自检、自测技巧,是参加ACM ICPC、Google...
一些相对独立的实用程序已经被排除在这个 repo 之外,以简化实现并使其部分用于其他目的。请注意,其中一些已记录在案(例如autodiff 、hdkrs ),但有些则没有(例如gut )。概述包含的工具和库在目录中组织如下...
SIGGRAPH论文“动态折射物体的交互式照明”的实现[ACM Trans。 图形。 [27,3,Article 35,2008]] [孙X.,周K.,斯托尔尼茨E.,史J.,郭B. ===== ![bunny](doc / bunnyres.PNG?raw = true) ![ball1](doc /...
韩文弢 -《论C++语言在信息学竞赛中的应用》 ## 2005 龙 凡 -《序的应用》 魏 冉 -《浅谈“跳跃表”的相关操作及其应用》 任 恺 -《图论的基本思想及方法》 杨 俊 -《二分策略在信息学竞赛中的应用》 张...
本书的目标读者是准备去硅谷找工作的码农,也适用于在国内找工作的码农,以及刚接触ACM算法竞赛的新手。 市场上讲解算法的书已经汗牛充栋,为什么还要写这本书呢?主要原因是我对目前市场上的大部分算法书都不太...