区间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)，序列中的数<=10⁶。

#include<stdio.h>
//区间k大数查询
int main()
{
	int i = 0,n = 0,m = 0,j = 0,p = 0,temp = 0;
	int a[1000],b[1000];
	scanf("%d",&n);//输入序列长度
	for( i = 0; i < n; i++ )//输入序列元素
	{
		scanf("%d",&a[i]);	
	}
	scanf("%d",&m);//输入询问个数
	while( m-- )
	{
		int l = 0,r = 0,k = 0;
		scanf("%d%d%d",&l,&r,&k);
		for( i = l - 1; i <= r - 1; i++ )//将l到r之间的元素放在一个新数组中
		{	
			b[j++] = a[i];
			p++;
		}
		for( i = 0; i < p; i++ )//对新数组从大到小进行排序
		{	
			for( j = p - 1; j > i; j-- )
			{
				if( b[j] > b[j-1])
				{
					temp = b[j-1];
					b[j-1] = b[j];
					b[j] = temp;	
				}
			}
		}	
		printf("%d\n",b[k-1]);//输出新数组中第k大的元素
		while(j--)
		{
			b[j] = 0;
		}	
		j = 0;
		p = 0;
		temp = 0;//对局部变量清零，以满足下次循环使用，此步骤十分重要
	}
	return 0;
}

首先需要两个数组，一个数组存放序列元素，另一个数组存放待查询的元素，再对待查询的元素进行从大到小排序，然后输出即可，关键不能忽略每次循环结束之后都必须对变量清零，其实思路并不复杂，开始看错题目条件了，误入歧途，接着有忽略清零这个过程，导致花了不少时间才最终得出结果。拥有缜密的逻辑思维以及持久的耐心是成功解决此类问题的关键所在。切记心浮气躁，急于求成。

秒客网

区间K大数查询

相关文章