Задача

5/6

std::nth_element

Теория Нажмите, чтобы прочитать/скрыть

nth_element - функция, которая позволяет находить n-ый элемент в массиве в отсортированном порядке за линейное время.
Функция принимает левую границу массива, итератор на позицию, значение которой в отсортированном порядке необходимо найти и правую границу массива.
После применения функции на указанном по итератору месте будет находиться необходимое значение, при этом остальные значения приобретут хаотичный порядок, но левее n-ого будут значения не больше его, а правее не меньше. То есть стоит понимать, что эта функция рушит исходный порядок элементов.
Подробнее можете прочитать в документации (https://www.cplusplus.com/reference/algorithm/nth_element/).

Пример: 

	vector 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 <= $
 

Задача

Вам дано q запросов. Каждый запрос задается массивом целых чисел размера ni и числом k. Вам необходимо вывести k-ое число в отсортированном порядке данного массива.

Входные данные:
В первой строке дано число q (1 <= q <= 20) - число запросов.
Далее идет описание запросов. 
Для каждого запроса в первой строке дается размер массива ni (1 <= ni <= 5000) и число k (1 <= k <= ni).
В следующей строке дается ni целых чисел - элементы массива, каждое из которых не превосходит 109 по абсолютной величине.

Выходные данные:
Выведите q чисел - ответы на запросы, каждый в отдельной строке.

Пример:
 
Входные данные Выходные данные
2
4 2
-5 3 4 3
3 3
-1 -2 -3		 3
-1




time 500 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Комментарий учителя

Вставьте недостающие фрагменты кода
C++
Напишите программу ниже 
#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;
}

     

Результат проверки программы 

Для проверки решения задачи необходимо зарегистрироваться или авторизоваться!