Problem

5/6

الأمراض المنقولة جنسيا :: 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 ، $ ، $ ، $ ، $ ، $] // حيث # & lt ؛ = 4 و 4 & lt ؛ = $ نبسب ؛

Problem

لقد تلقيت استفسارات q. يتم تقديم كل طلب بواسطة مصفوفة من الأعداد الصحيحة بالحجم n i ورقم k. تحتاج إلى إخراج الرقم k بالترتيب الفرز للمصفوفة المحددة.

الإدخال:
يحتوي السطر الأول على الرقم q (1 & lt؛ = q & lt؛ = 20) - عدد الاستعلامات.
فيما يلي وصف للطلبات. & nbsp؛
لكل استعلام ، يعطي السطر الأول حجم المصفوفة n i (1 & lt؛ = n i & lt؛ = 5000) والرقم k (1 & lt؛ = k & lt؛ = n i ).
يحتوي السطر التالي على n i أعداد صحيحة - عناصر مصفوفة ، كل منها لا يتجاوز 10 9 في القيمة المطلقة.

الإخراج:
اطبع أرقام 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!