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!