ACM第K个数 C++实现

喜欢ヅ旅行 2022-05-15 13:17 109阅读 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 条评论，109人围观）

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

相关阅读

相关 786. 第k个数

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

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

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

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

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

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

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

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

相关第k个数

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

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

相关 46：最小的第K个数

最小的第K个数 public class Offer46 { //基于快速排序的基础partition()方法 pub

缺乏、安全感/ 2022年11月25日 13:11/ 0 赞/ 103 阅读

相关第k个数

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

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

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

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

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

相关 acm 1的个数

1的个数时间限制：3000 ms | 内存限制：65535 KB 难度：1 输入第一行输入一个整数N，表示测试数据的组数(1<N<1000) 每组测试数

柔情只为你懂/ 2022年05月17日 21:04/ 0 赞/ 113 阅读

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

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

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

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

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

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