Problem

2/6

Lower_bound / upper_bound

Theory Click to read/hide

low_bound و upper_bound وظائف بحث ثنائية مضمنة.

low_bound - دالة تجد ، في الوقت اللوغاريتمي ، أصغر عنصر في مصفوفة مرتبة أكبر من أو تساوي القيمة المعطاة k.
يأخذ حدود المصفوفة وقيمة k كوسيطات.
إرجاع مكرر إلى العنصر الموجود ، أو إلى نهاية (غير مدرج) المصفوفة في حالة عدم وجود مثل هذا العنصر.
يمكنك قراءة المزيد في الوثائق .

upper_bound - دالة تجد في الوقت اللوغاريتمي في مصفوفة مرتبة أصغر عنصر أكبر من القيمة المعطاة k.
يأخذ حدود المصفوفة وقيمة k كوسيطات.
إرجاع مكرر إلى العنصر الموجود ، أو إلى نهاية (غير مدرج) المصفوفة في حالة عدم وجود مثل هذا العنصر.
يمكنك قراءة المزيد في الوثائق .

تجدر الإشارة إلى أن استخدام هذه الوظائف على مجموعة أو مجموعة متعددة لا يعمل في الوقت اللوغاريتمي بسبب نقص التكرارات في مجموعات الوصول العشوائية المذكورة أعلاه.
ومع ذلك ، فإن هذه المجموعات لها طرق مضمنة مقابلة (أي أنك تحتاج إلى استخدامها "من خلال نقطة").

أمثلة:
نبسب ؛ المتجه a = {0، 1، 3، 5، 7} ؛ متجه :: مكرره ؛ it = lower_bound (a.begin () ، a.end () ، 4) ؛ // * هو == 5 it = low_bound (a.begin () ، a.end () ، 5) ؛ // * هو == 5 it = low_bound (a.begin () ، a.end () ، 8) ؛ // it == a.end () it = upper_bound (a.begin ()، a.end ()، 4) ؛ // * هو == 5 it = upper_bound (a.begin ()، a.end ()، 5) ؛ // * هو == 7 it = upper_bound (a.begin () ، a.end () ، -1) ؛ // * هو == 0 // عن طريق طرح التكرارات ، يمكنك الحصول على فهرس العنصر الذي تم العثور عليه int ind = lower_bound (a.begin () ، a.end () ، 4) - a.begin () ؛ // ind == 3 // تحتاج إلى استخدام طرق بدلاً من وظائف للمجموعات والمجموعات المماثلة ضبط s {1، 3، 5} ؛ ضبط :: iterator sit؛ الجلوس = s.lower_bound (3) ؛ // * الجلوس == 3 الجلوس = s.upper_bound (3) ؛ // * الجلوس == 5 نبسب ؛

Problem

تحصل على مصفوفة مرتبة A تتكون من n أعداد طبيعية. & nbsp؛
هناك طلبات ف لتتم معالجتها. يتم إعطاء كل استعلام معلمتين - نوعه t i والرقم k i .

وصف الاستعلامات حسب نوعها:
1) ابحث في A عن الحد الأدنى للرقم الذي لا يقل عن k i .
2) ابحث عن الحد الأدنى للرقم في A والذي هو أكبر من k i .
3) ابحث في A عن العدد الأقصى الذي لا يزيد عن k i .
4) أوجد العدد الأقصى في A الذي يقل تمامًا عن k i .

لكل استعلام ، قم بالإبلاغ عن الرقم الذي تم العثور عليه ، أو -1 إذا لم يكن موجودًا.

الإدخال:
يحتوي السطر الأول على الرقم n (1 & lt؛ = n & lt؛ = 10 5 ) - عدد عناصر المصفوفة أ.
يحتوي السطر الثاني على n أعداد طبيعية A i (1 & lt؛ = A i & lt؛ = 10 9 ) - عناصر المصفوفة نفسها. علاوة على ذلك ، بالنسبة للجميع أنا العلامة & lt ؛ تم إنجاز n A i & lt؛ = A i + 1 .
يحتوي السطر الثالث على الرقم q (1 & lt؛ = q & lt؛ = 10 5 ) - عدد الطلبات.
يحتوي سطور q التالية على رقمين لكل منهما - t i (1 & lt؛ = t ​​ i & lt؛ = 4) و k i (1 & lt ؛ = k i & lt؛ = 10 9 ).

الإخراج:
اطبع سطورًا ، رقم واحد - الإجابة على الاستعلام الأول.

أمثلة:
نبسب ؛ <الجسم>
إدخال الإخراج
4
3 5 5 7
4
15
27
3 2
4 4 		5
-1
-1
3

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 query1(vector<int>& arr, int k) {
	vector<int>::iterator it =     
if (it ==     
)
		return -1;
	return *it;
}

int query2(vector<int>& arr, int k) {
	vector<int>::iterator it =     
if (it ==     
)
		return -1;
	return *it;
}

int query3(vector<int>& arr, int k) {
	vector<int>::iterator it =     
if (it ==     
)
		return -1;
	return *(--it);
}

int query4(vector<int>& arr, int k) {
	vector<int>::iterator it =   
if (it ==     
)
		return -1;
	return *(--it);
}
 
int main()
{
    // ускорение ввода и вывода
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int n;
	cin >> n;

	vector<int> arr(n);
	for (int i = 0; i < n; i++)
		cin >> arr[i];

	int q;
	cin >> q;

	while (q--) {
		int type, k;
		cin >> type >> k;

		if (type == 1)
			cout << query1(arr, k) << endl;
		if (type == 2)
			cout << query2(arr, k) << endl;
		if (type == 3)
			cout << query3(arr, k) << endl;
		if (type == 4)
			cout << query4(arr, k) << endl;
	}
	
	return 0;
}

     

Program check result

To check the solution of the problem, you need to register or log in!