ACM第K个数 C++实现

待我称王封你为后i 2022-05-15 13:18 132阅读 0赞

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

发表评论取消回复

表情：

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

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

相关阅读

相关 786. 第k个数

给定一个长度为nn的整数数列，以及一个整数kk，请用快速选择算法求出数列从小到大排序后的第kk个数。输入格式第一行包含两个整数nn和kk。第二行包含nn个整数（所有整数均...

迷南。/ 2024年05月01日 16:06/ 0 赞/ 71 阅读

相关第k个数(c++, java)

第k个数(c++, java) 给定一个长度为 n的整数数列，以及一个整数 k，请用快速选择算法求出数列从小到大排序后的第 k 个数。输入格式第一行包含两个整数 n

雨点打透心脏的1/2处/ 2024年03月25日 08:56/ 0 赞/ 74 阅读

相关第k个数（快速排序）

7-5 第k个数 (20 分) 知识点：快速排序给定一个长度为 n 的整数数列，以及一个整数 k，请用快速选择算法求出数列从小到大排序后的第 k 个数。输入格式:

港控/mmm°/ 2023年10月11日 16:24/ 0 赞/ 48 阅读

相关（每日一练c++）CC179 第k个数

前言 C++是一种计算机高级程序设计语言，由C语言扩展升级而产生，最早于1979年由本贾尼·斯特劳斯特卢普在AT&T贝尔工作室研发。 C++既可以进行C语言的过程化

叁歲伎倆/ 2023年10月04日 18:03/ 0 赞/ 44 阅读

相关快速排序查询第k个数

给定一个长度为 n 的整数数列，以及一个整数 k，请用快速选择算法求出数列从小到大排序后的第 k 个数。输入格式第一行包含两个整数 n 和 k。第二行包含 n 个

╰+哭是因爲堅強的太久メ/ 2023年09月30日 11:06/ 0 赞/ 8 阅读

相关第k个数

给定一个长度为n的整数数列，以及一个整数k，请用快速选择算法求出数列的第k小的数是多少。输入格式第一行包含两个整数 n 和 k。第二行包含 n 个整数（所有整

本是古典何须时尚/ 2022年12月04日 01:22/ 0 赞/ 155 阅读

相关第k个数

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

今天药忘吃喽~/ 2022年11月04日 09:03/ 0 赞/ 130 阅读

相关 ACM第K个数 C++实现

第K个数 Description 给你一个整数序列和若干个问题，问题是这个序列的第i个元素到第j个元素的片断中的第k大数是什么？比如说给你的序列为（1, 5, 2,

╰半夏微凉°/ 2022年06月18日 11:27/ 0 赞/ 132 阅读

相关 ACM第K个数 C++实现

第K个数 Description 给你一个整数序列和若干个问题，问题是这个序列的第i个元素到第j个元素的片断中的第k大数是什么？比如说给你的序列为（1, 5, 2,

待我称王封你为后i/ 2022年05月15日 13:18/ 0 赞/ 133 阅读

相关 ACM第K个数 C++实现

第K个数 Description 给你一个整数序列和若干个问题，问题是这个序列的第i个元素到第j个元素的片断中的第k大数是什么？比如说给你的序列为（1, 5, 2,

喜欢ヅ旅行/ 2022年05月15日 13:17/ 0 赞/ 156 阅读