Problem

5/6

std::nth_element

Theory Click to read/hide

nth_element é uma função que permite encontrar o n-ésimo elemento em uma matriz em ordem de classificação em tempo linear.
A função pega a extremidade esquerda da matriz, um iterador para a posição cujo valor na ordem de classificação deve ser encontrado e a extremidade direita da matriz.
Após a aplicação da função, o valor necessário estará localizado no local indicado pelo iterador, enquanto os valores restantes adquirirão uma ordem caótica, mas à esquerda do enésimo haverá valores não mais que isso, e para a direita não menos. Ou seja, deve-se entender que esta função destrói a ordem original dos elementos.
Você pode ler mais na documentação (https://www.cplusplus.com/reference/algorithm/nth_element/).

Exemplo: vetor a = { 4, 0, 3, 9, 2, 1, 8, 5, 6, 7 }; // procura elemento no índice 4 // presta atenção na ordem dos argumentos nth_element(a.begin(), a.begin() + 4, a.end()); // a = [#, #, #, #, 4, $, $, $, $, $] // onde # <= 4 e 4 <= $  

Problem

Você recebe perguntas q. Cada requisição é dada por um array de inteiros de tamanho ni e um número k. Você precisa produzir o k-ésimo número na ordem de classificação do array fornecido.

Entrada:
A primeira linha contém o número q (1 <= q <= 20) - o número de consultas.
A seguir está uma descrição das solicitações. 
Para cada consulta, a primeira linha fornece o tamanho da matriz ni (1 <= ni <= 5000) e o número k (1 <= k <= n i).
A próxima linha contém ni inteiros - elementos da matriz, cada um dos quais não excede 109 em valor absoluto.

Saída:
Imprima q números - as respostas das perguntas, cada uma em uma linha separada.

Exemplo:
 
Entrada Saída
2
4 2
-5 3 4 3
3 3
-1 -2 -3 		3
-1


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++
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!