Problem

5/6

std::nth_element

Theory Click to read/hide

nth_element 是一个函数，可让您在线性时间内按排序顺序查找数组中的第 n 个元素。
该函数采用数组的左端、指向要查找其值的位置的迭代器以及数组的右端。
应用该函数后，所需的值将位于迭代器指示的位置，而剩余的值将获得混乱的顺序，但第n个左边的值将不超过它，并且向右不少。即应该理解为这个函数破坏了元素原有的顺序。
您可以在文档 (https://www.cplusplus.com/reference/algorithm/nth_element/) 中阅读更多内容。

例子： 矢量 a = { 4, 0, 3, 9, 2, 1, 8, 5, 6, 7 }; // 查找索引为 4 的元素 // 注意参数的顺序 nth_element(a.begin(), a.begin() + 4, a.end()); // a = [#, #, #, #, 4, $, $, $, $, $] // 其中 # <= 4 和 4 <= $  

Problem

你有 q 个查询。每个请求都由一个大小为 ni 的整数数组和一个数字 k 给出。您需要按照给定数组的排序顺序输出第 k 个数字。

输入：
第一行包含数字 q (1 <= q <= 20) - 查询数。
以下是对请求的描述。 
对于每个查询，第一行给出数组的大小 ni (1 <= ni <= 5000) 和数字 k (1 <= k <= n i).
下一行包含 ni 个整数——数组元素，每个元素的绝对值不超过 109。

输出：
打印 q 个数字 - 问题的答案，每个都在单独的一行上。

示例：
  <正文>

time 500 ms
memory 256 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Insert the missing code snippets
C++
输入 输出
2
4 2
-5 3 4 3
3 3
-1 -2 -3 		3
-1
Write the program below 
#include <bits/stdc++.h>
using namespace std;
 
int main()
{
    int q;
	cin >> q;

	while (q--) {
		int n, k;
		cin >> n >> k;

		vector<int> arr(n);
		for (int i = 0; i < n; i++)
			cin >> arr[i]; 
	}
	
	return 0;
}

     

Program check result

To check the solution of the problem, you need to register or log in!