Part1试题 算法训练 区间k大数查询
资源限制
时间限制:1.0s 内存限制:256.0MB
问题描述
给定一个序列,每次询问序列中第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。
Part2题解:C语言
很简单,按题目要求老老实实做
#include<stdio.h>
int devide(long a[], int low, int high) {
long key = a[high];
while (low<high) {
while (low<high&&a[low]>key) {
low++;
}
if (low<high)
a[high--] = a[low];
while (low<high&&a[high]<key) {
high--;
}
if (low<high)
a[low++] = a[high];
}
a[high] = key;
return high;
}
void sort(long a[], int low, int high) {
if (low>high) {
return;
}
int j;
j = devide(a, low, high);
sort(a, low, j - 1);
sort(a, j + 1, high);
}
int main() {
int n, i, j;
long a[1000], b[1000];
int m;
int l, r, k;
scanf("%d", &n);
for (i = 0; i<n; i++) {
scanf("%ld", &a[i]);
}
scanf("%d", &m);
for (i = 0; i<m; i++) {
for (j = 0; j<n; j++) {
b[j] = a[j];
}
scanf("%d%d%d", &l, &r, &k);
sort(b, l - 1, r - 1);
printf("%dn", b[l + k - 2]);
}
return 0;
}
简化代码:
#include <stdio.h>
#define N 1000
int arr[N] = {0};
int max_sort(int l,int r,int k);
int main(void)
{
int i = 0 , j = 0 ;
int l = 0 , r = 0 , k = 0 ;
int n = 0 , m = 0 ;
int tmp[N][3] = {0};
scanf("%d",&n); /*序列长度*/
for (i = 0 ; i < n ; i ++)
{
scanf("%d",&arr[i]); /*给定的序列*/
}
scanf("%d",&m); /*询问的个数*/
for (i = 0 ; i < m ; i ++)
{
scanf("%d %d %d",&tmp[i][0],&tmp[i][1],&tmp[i][2]);
}
for (i = 0 ; i < m ; i ++)
{
printf("%dn",max_sort(tmp[i][0],tmp[i][1],tmp[i][2]));
}
return 0;
}
/*
在第l个数~第r个数中,找出第k大的数
*/
int max_sort(int l,int r,int k)
{
int max = 0 ;
int tmp[N] = {0};
int i = 0 , j = 0 ;
for (i = 0 ; i <= r-l ; i ++)
{
tmp[i] = arr[l-1+i];
}
for (i = 0 ; i <= r-l ; i ++)
{
for (j = i + 1 ; j <= r-l ; j ++)
{
if (tmp[i] < tmp[j])
{
tmp[i] = tmp[i] ^ tmp[j];
tmp[j] = tmp[i] ^ tmp[j];
tmp[i] = tmp[i] ^ tmp[j];
}
}
}
return tmp[k-1];
}
本文为CSDN博主「tonyhapply」的原创文章,原文链接:https://blog.csdn.net/tonyhapply/article/details/107740011
原文始发于微信公众号(HackerDo安全):算法篇-ALGO-1 区间k大数查询 (排序、查找)C语言 | HackerDo安全
免责声明:文章中涉及的程序(方法)可能带有攻击性,仅供安全研究与教学之用,读者将其信息做其他用途,由读者承担全部法律及连带责任,本站不承担任何法律及连带责任;如有问题可邮件联系(建议使用企业邮箱或有效邮箱,避免邮件被拦截,联系方式见首页),望知悉。
- 左青龙
- 微信扫一扫
-
- 右白虎
- 微信扫一扫
-
评论