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 را چاپ کنید - پاسخ سوالات، هر کدام در یک خط جداگانه.

مثال:
  <بدن>
ورودی خروجی
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!