Problem

5/6

std::nth_element

Theory Click to read/hide

nth_element는 선형 시간으로 정렬된 순서로 배열에서 n번째 요소를 찾을 수 있게 해주는 함수입니다.
이 함수는 배열의 왼쪽 끝, 정렬된 순서로 값을 찾을 위치의 반복자, 배열의 오른쪽 끝을 가져옵니다.
함수 적용 후 필요한 값은 iterator가 가리키는 곳에 위치하게 되고, 나머지 값들은 혼돈의 순서를 가지게 되지만 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!