本题翻译自 [HDU6231] K-th Number 。其前身为 2017 CCPC中国大学生程序设计竞赛(哈尔滨站)试题。 对于给定的由 个元素组成的数组 ,你需要按照下方的规则构建一个新的数组 : 初始时数组 为空; 随后,对于数组 中的每一个长度大于等于 的区间,找到该区间的第 大元素,将这个元素添加到数组 中; 重复上述操作,直到数组 中所有长度大于等于 的区间都被检查完毕; 最后,直接输出数组 中的第 大元素。
输入描述:
每个测试文件包含多组测试数据。第一行输入一个整数 代表数据组数,每组测试数据描述如下:第一行输入三个整数 代表数组 中的元素数量、区间限定长度、需要输出的元素在数组 中的下标。保证 存在。第二行输入 个整数 代表数组 中的元素。


输出描述:
对于每组测试数据,在一行上输出一个整数,代表数组 中的第 大元素。
示例1

输入

6
5 3 1
2 3 1 5 4
5 3 2
2 3 1 5 4
5 3 3
2 3 1 5 4
5 3 4
2 3 1 5 4
5 3 5
2 3 1 5 4
3 3 1
5 8 2

输出

3
3
2
1
1
2

说明

\hspace{15pt}在前五组测试数据中,数组 a\{2,3,1,5,4\} ,长度大于等于 k=3 的区间有:
\hspace{23pt}\bullet\, [1, 3] 排序后得到 \{1, 2, 3\} ;
\hspace{23pt}\bullet\, [2, 4] 排序后得到 \{1, 3, 5\} ;
\hspace{23pt}\bullet\, [3, 5] 排序后得到 \{1, 4, 5\} ;
\hspace{23pt}\bullet\, [1, 4] 排序后得到 \{1, 2, 3, 5\} ;
\hspace{23pt}\bullet\, [2, 5] 排序后得到 \{1, 3, 4, 5\} ;
\hspace{23pt}\bullet\, [1, 5] 排序后得到 \{1, 2, 3, 4, 5\} ;
\hspace{15pt}因此数组 b 即为 \{1, 1, 1, 2, 3, 3\}
加载中...