• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

区间 k 大数查询

开发技术 开发技术 4小时前 1次浏览

问题描述

给定一个序列,每次询问序列中第 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。

解题思路与想法

看这题我看的的确不是很懂,我的理解是输入一个数n代表数组的长度,然后输入数据
不知道数据是不是乱序,所以我把数据给重新排序了一遍
排序之后再输入一个范围,这个范围我用数组b【】来储存,然后在范围里找第K大的数
找到之后输出,我的理解就是这样,但输出和输入的跟题目不一样,所以今晚好好听题

代码如下

#include <iostream>
#include <string >
using namespace std;
void main() {
	int n = 0;
	cin>>n;
	int i;
	int j;
	int temp;
	int a[1000];
	for(i=0;i<n;i++){
		cin>>a[i];
	}
	for(i=0;i<n;i++){
		for(j=0;j<n;j++){
			if(a[i]<a[j]){
				temp = a[i];
				a[i] = a[j];
				a[j] = temp;
			}
		}
	}
	//排序完成
	int b[1000];
	int i1;
	int i2;
	int y;
	cin>>i1>>i2;
	i2=i2-i1;
	for(y=0;y<=i2;y++){
		b[y]=a[i1-1];
		i1=i1+1;
	}
	//找到数范围数并且存到b【】里
	int K;
	cin>>K;
	cout<<b[y+1-K];
	cout<<K;
	return ;
}

程序员灯塔
转载请注明原文链接:区间 k 大数查询
喜欢 (0)