区间k大数查询

发布时间：2020-12-14 01:25:40 所属栏目：大数据来源：网络整理

导读：问题描述给定一个序列，每次询问序列中第l个数到第r个数中第K大的数是哪个。输入格式第一行包含一个数n，表示序列长度。第二行包含n个正整数，表示给定的序列。第三个包含一个正整数m，表示询问个数。接下来m行，每行三个数l,r,K，表示询问序列从左往

问题描述

给定一个序列，每次询问序列中第l个数到第r个数中第K大的数是哪个。

输入格式

第一行包含一个数n，表示序列长度。

第二行包含n个正整数，表示给定的序列。

第三个包含一个正整数m，表示询问个数。

接下来m行，每行三个数l,r,K，表示询问序列从左往右第l个数到第r个数中，从大往小第K大的数是哪个。序列元素从1开始标号。

输出格式

总共输出m行，每行一个数，表示询问的答案。

样例输入

样例输出

    4 
   
 2

数据规模与约定

对于30%的数据，n,m<=100；

对于100%的数据，n,m<=1000；

保证k<=(r-l+1)，序列中的数<=106。

我写的对是对的但输入输出格式不符合题意，有空将其补上

思路：

? ? ? ? 对按输入的第几个到第几个的区间的元素进行排序，在已经排序的后的区间里找出第几大的元素即可

代码：

#include <stdio.h>
main()
{
	int a[100],b[100],i,j,n,k,s=1,c,t,m,x,y,z;
	scanf("%d",&n);
	for (i=0;i<n;i++)
		scanf("%d",&a[i]);
	scanf("%d",&m);

		for (c=0;c<n;c++)        //把a数组赋值给b数组
			b[c]=a[c];
for (i=0;i<m;i++){scanf("%d%d%d",&x,&y,&z);for (j=x-1;j<y-1;j++) //对数组中第x个到第y个数中进行排序，求第z大的数即是数组xy区间中z-1号下标的元素{for (k=j+1;k<y;k++){if (b[j]<b[k]){t=b[j];b[j]=b[k];b[k]=t;}}}printf("%d",b[z-1]);}}





 
 
  
  		for (c=0;c<n;c++)        //每次都要给b数组
			b[c]=a[c];

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!