首页 > 代码库 > C语言 · 区间K大数查询

C语言 · 区间K大数查询

2024-08-31 13:55:56   221人阅读

问题描述

给定一个序列，每次询问序列中第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)，序列中的数<=106。

 
作者思路：输入序列（记录好原序），输入查询的个数（就是题中的m），定义int c[m]——用来记录每一个答案，准备在最后分行输出；输入l、r、K，注意：没输入一组l、r、K要记得将数组返回原序。
 
 1 #include<stdio.h>
 2 #include<algorithm>
 3 using namespace std;
 4 bool cmp(int a, int b){
 5     return a>b;
 6 }
 7 
 8 int main(){
 9     int N,m;//N表示序列长度 ,m示询问的个数 
10     int l,r,K;//表示查询数列从第l个到第r个数之间 ，第K大的数是多少 
11     scanf("%d",&N);
12     int a[N],b[N],f[N];
13     for(int i=0;i<N;i++){
14         scanf("%d",&a[i]);
15         /*记录原序*/
16         f[i] = a[i];
17     }
18     
19     scanf("%d",&m);
20     int c[m];
21     for(int s=0;s<m;s++){
22         /*输入查询数列从第l个到第r个数之间 ，第K大的数*/
23         scanf("%d%d%d", &l, &r, &K);
24         for(int j = 0, i = l-1; i < r; i++){
25             b[j++] = a[i];
26         }
27         sort(b, b+r-l+1, cmp);
28         /*按条件将答案放入数组中*/
29         c[s] = b[K-1];
30         /*a返回原序*/
31         for(int i=0;i<N;i++){
32             a[i] = f[i];
33         }
34 //        printf("%d\n",c[m]);
35     }
36     /*按条件输出答案*/ 
37     for(int j=0;j<m;j++){
38         printf("%d\n",c[j]);
39     }
40 }

 

 
 
 

C语言 · 区间K大数查询


联系
我们