`
pleasetojava
  • 浏览: 698311 次
  • 性别: Icon_minigender_2
  • 来自: 上海
文章分类
社区版块
存档分类
最新评论

ACM第K个数 C++实现

 
阅读更多

第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;
}

分享到:
评论

相关推荐

    A*求K短路模板(有注释,c++实现)

    c++实现的A*算法求K短路模板,内有注释,根据注释代码很容易理解

    浙江大学ACM题解/ZJU 题型分类

    文演整理版 2008-3-23 数论: 1007 Numerical Summation of a Series 简单题,还是蛮有意思的 1045 HangOver 简单题 1049 I Think I Need a Houseboat 简单题 1028 Flip and Shift 简单题,可以DP/BFS/……,...

    伯努利装错信封问题 {c++}

    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 &gt;= 3) { for (k = 1; k ; k++) { if (n &gt;= 4) { for (x = 1; x ; x++) { if (n &gt;= 5) ...

    红黑树C语言源码,基于一个具体问题

    红黑树的C语言实现,附加了顺序统计域,思想源自《算法导论》第三版ch13伪代码,基于的具体问题为:学校举办了一个在线ACM比赛,快速实现榜单的插入、删除、第k小查询

    leetcode过桥问题-leetcode-practice:Leetcode题,ACM题刷题汇总

    实现:利用C++实现各种数据结构和经典算法 KMP算法: 二叉树的创建,展示,以及、三种遍历方法(先根,后根,中跟)的递归非递归实现:/Cplus_algorithm/binTree.cpp 值得留意的题目:树相关。具体有: 参考: [394....

    angus-clipper:多边形和线剪裁和偏移库

    安格斯快船多边形和线剪裁和偏移库归因这个库中的代码是 Bala Vatti 裁剪算法的扩展:“多边形裁剪的通用解决方案” ACM 通讯,第 35 卷,第 7 期(1992 年 7 月)第 56-63 页。 计算机图形学和几何建模:实现和算法...

    高效算法:竞赛、应试与提高必修128例.[法] Christoph Dürr Jill-Jênn Vie(带书签文字版).pdf

    本书旨在探讨如何优化算法效率,详细阐述了经典算法和特殊算法的实现、应用技巧和复杂度验证过程,内容由浅入深,能帮助读者快速掌握复杂度适当、正确率高的高效编程方法以及自检、自测技巧,是参加ACM ICPC、Google...

    用于动画交互软对象的模拟工具

    一些相对独立的实用程序已经被排除在这个 repo 之外,以简化实现并使其部分用于其他目的。请注意,其中一些已记录在案(例如autodiff 、hdkrs ),但有些则没有(例如gut )。概述包含的工具和库在目录中组织如下...

    InteractiveRefractiveRelighting:动态折射物体的交互式照明

    SIGGRAPH论文“动态折射物体的交互式照明”的实现[ACM Trans。 图形。 [27,3,Article 35,2008]] [孙X.,周K.,斯托尔尼茨E.,史J.,郭B. ===== ![bunny](doc / bunnyres.PNG?raw = true) ![ball1](doc /...

    IOI国家集训队论文集1999-2019

    韩文弢 -《论C++语言在信息学竞赛中的应用》 ## 2005 龙 凡 -《序的应用》 魏 冉 -《浅谈“跳跃表”的相关操作及其应用》 任 恺 -《图论的基本思想及方法》 杨 俊 -《二分策略在信息学竞赛中的应用》 张...

    cpp-算法精粹

    本书的目标读者是准备去硅谷找工作的码农,也适用于在国内找工作的码农,以及刚接触ACM算法竞赛的新手。 市场上讲解算法的书已经汗牛充栋,为什么还要写这本书呢?主要原因是我对目前市场上的大部分算法书都不太...

Global site tag (gtag.js) - Google Analytics