Problem

5/6

std::nth_element

Theory Click to read/hide

nth_element là hàm cho phép bạn tìm phần tử thứ n trong mảng theo thứ tự đã sắp xếp theo thời gian tuyến tính.
Hàm lấy phần cuối bên trái của mảng, một trình vòng lặp đến vị trí có giá trị theo thứ tự được sắp xếp sẽ được tìm thấy và phần cuối bên phải của mảng.
Sau khi áp dụng hàm, giá trị cần thiết sẽ được đặt tại vị trí được chỉ định bởi trình vòng lặp, trong khi các giá trị còn lại sẽ có thứ tự hỗn loạn, nhưng ở bên trái của thứ n sẽ có các giá trị không nhiều hơn nó và bên phải không ít. Nghĩa là, nên hiểu rằng hàm này phá bỏ thứ tự ban đầu của các phần tử.
Bạn có thể đọc thêm trong tài liệu (https://www.cplusplus.com/reference/algorithm/nth_element/).

Ví dụ: vectơ a = { 4, 0, 3, 9, 2, 1, 8, 5, 6, 7 }; // tìm phần tử ở chỉ số 4 // chú ý đến thứ tự của các đối số nth_element(a.begin(), a.begin() + 4, a.end()); // a = [#, #, #, #, 4, $, $, $, $, $] // trong đó # <= 4 và 4 <= $  

Problem

Bạn được cung cấp q truy vấn. Mỗi yêu cầu được đưa ra bởi một mảng các số nguyên có kích thước ni và một số k. Bạn cần xuất số thứ k theo thứ tự đã sắp xếp của mảng đã cho.

Đầu vào:
Dòng đầu tiên chứa số q (1 <= q <= 20) - số truy vấn.
Sau đây là mô tả về các yêu cầu. 
Đối với mỗi truy vấn, dòng đầu tiên cho biết kích thước của mảng ni (1 <= ni <= 5000) và số k (1 <= k <= n i).
Dòng tiếp theo chứa ni số nguyên - phần tử mảng, mỗi số không vượt quá 109 về giá trị tuyệt đối.

Đầu ra:
In ra q số - đáp án cho các câu hỏi, mỗi số trên một dòng riêng.

Ví dụ:
 

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++
Đầu vào Đầu ra
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!