Problem

5/6

std :: nth_element

Theory Click to read/hide

nth_element est une fonction qui vous permet de trouver le nième élément d'un tableau dans un ordre trié en temps linéaire.
La fonction prend l'extrémité gauche du tableau, un itérateur à la position dont la valeur dans l'ordre trié doit être trouvée, et l'extrémité droite du tableau.
Après avoir appliqué la fonction, la valeur requise sera située à l'endroit indiqué par l'itérateur, tandis que les valeurs restantes acquerront un ordre chaotique, mais à gauche du nième, il n'y aura pas plus de valeurs qu'elle, et à droite pas moins. Autrement dit, il faut comprendre que cette fonction détruit l'ordre d'origine des éléments.
Vous pouvez en savoir plus dans la documentation (https://www.cplusplus.com/reference/algorithm/nth_element/).

Exemple: vecteur a = { 4, 0, 3, 9, 2, 1, 8, 5, 6, 7 } ; // recherche l'élément à l'index 4 // attention à l'ordre des arguments nth_element(a.begin(), a.begin() + 4, a.end()); // un = [#, #, #, #, 4, $, $, $, $, $] // où # <= 4 et 4 <= $  

Problem

On vous donne q requêtes. Chaque requête est donnée par un tableau d'entiers de taille ni et un nombre k. Vous devez afficher le kème nombre dans l'ordre trié du tableau donné.

Saisie :
La première ligne contient le nombre q (1 <= q <= 20) - le nombre de requêtes.
Voici une description des demandes. 
Pour chaque requête, la première ligne donne la taille du tableau ni (1 <= ni <= 5000) et le nombre k (1 <= k <= n i).
La ligne suivante contient ni entiers - éléments de tableau, dont chacun ne dépasse pas 109 en valeur absolue.

Sortie :
Imprimer q numéros - les réponses aux questions, chacune sur une ligne distincte.

Exemple :
 
Entrée Sortie
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!