NC14354. 区间排序
描述
给定一个序列，每次询问序列中第l个数到第r个数中第K大的数是哪个。
输入描述
第一行包含一个数n，表示序列长度。
第二行包含n个正整数，表示给定的序列。
第三个包含一个正整数m，表示询问个数。
接下来m行，每行三个数l,r,K，表示询问序列从左往右第l个数到第r个数中，从大往小第K大的数是哪个。序列元素从1开始标号。
输出描述
总共输出m行，每行一个数，表示询问的答案。
示例1
输入:
5 1 2 3 4 5 2 1 5 2 2 3 2
输出:
4 2
C++(clang++11) 解法, 执行用时: 23ms, 内存消耗: 476K, 提交时间: 2020-12-10 17:52:57
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin>>n;
int a[n+5],b[n+5];
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
int m;
cin>>m;
while(m--)
{
int l,r,k,t=0;
cin>>l>>r>>k;
for(int i=l;i<=r;i++)
{
b[t++]=a[i];
}
sort(b,b+t,greater<int>());
cout<<b[k-1]<<endl;
}
}
Python3 解法, 执行用时: 93ms, 内存消耗: 4728K, 提交时间: 2023-04-16 19:43:53
n=int(input())
a=list(map(int,input().split()))
for i in range(int(input())):
l,r,K=map(int,input().split())
b=sorted(a[l-1:r])
print(b[-K])