Problem

2/6

Lower_bound/upper_bound

Theory Click to read/hide

Lower_bound và upper_bound là các hàm tìm kiếm nhị phân được tích hợp sẵn.

Lower_bound - một hàm, theo thời gian logarit, tìm phần tử nhỏ nhất trong một mảng đã sắp xếp lớn hơn hoặc bằng giá trị k đã cho.
Nó lấy giới hạn của mảng và giá trị của k làm đối số.
Trả về một trình vòng lặp cho phần tử tìm thấy hoặc đến phần cuối (không bao gồm) của mảng nếu không có phần tử nào như vậy tồn tại.
Bạn có thể đọc thêm trong tài liệu.

upper_bound - một hàm theo thời gian logarit trong một mảng đã sắp xếp sẽ tìm phần tử nhỏ nhất lớn hơn giá trị k đã cho.
Nó lấy giới hạn của mảng và giá trị của k làm đối số.
Trả về một trình vòng lặp cho phần tử tìm thấy hoặc đến phần cuối (không bao gồm) của mảng nếu không có phần tử nào như vậy tồn tại.
Bạn có thể đọc thêm trong tài liệu.

Cần làm rõ rằng việc sử dụng các hàm này trên một tập hợp hoặc nhiều tập hợp không hoạt động trong thời gian logarit do thiếu bộ lặp trong các tập hợp truy cập ngẫu nhiên ở trên.
Tuy nhiên, các bộ sưu tập này có các phương thức tích hợp sẵn tương ứng (nghĩa là bạn cần sử dụng chúng "thông qua dấu chấm").

Ví dụ:
  vectơ a = { 0, 1, 3, 5, 7 }; vector::iterator it; nó = Lower_bound(a.begin(), a.end(), 4); // * nó == 5 nó = Lower_bound(a.begin(), a.end(), 5); // * nó == 5 nó = Lower_bound(a.begin(), a.end(), 8); // nó == a.end() it = upper_bound(a.begin(), a.end(), 4); // * nó == 5 it = upper_bound(a.begin(), a.end(), 5); // * nó == 7 it = upper_bound(a.begin(), a.end(), -1); // * nó == 0 // bằng cách trừ đi các vòng lặp, bạn có thể lấy chỉ mục của phần tử được tìm thấy int ind = Lower_bound(a.begin(), a.end(), 4) - a.begin(); // ind == 3 // cần sử dụng các phương thức thay vì các hàm cho tập hợp và các tập hợp tương tự tập hợp s{ 1, 3, 5 }; set::iterator ngồi; ngồi = s.lower_bound(3); // *ngồi == 3 ngồi = s.upper_bound(3); // *ngồi == 5  

Problem

Bạn được cung cấp một mảng A có thứ tự gồm n số tự nhiên. 
Có q yêu cầu được xử lý. Mỗi truy vấn được cung cấp hai tham số - loại ti và số ki.

Mô tả truy vấn theo loại:
1) Tìm trong A số nhỏ nhất không nhỏ hơn ki.
2) Tìm số nhỏ nhất trong A lớn hơn ki.
3) Tìm trong A số lớn nhất không lớn hơn ki.
4) Tìm số lớn nhất trong A hoàn toàn nhỏ hơn ki.

Đối với mỗi truy vấn, hãy báo cáo số được tìm thấy hoặc -1 nếu không tồn tại.

Đầu vào:
Dòng đầu tiên ghi số n (1 <= n <= 105) - số phần tử của mảng A.
Dòng thứ hai chứa n số tự nhiên Ai (1 <= Ai <= 109) - chính các phần tử của mảng. Hơn nữa, đối với tất cả tôi < xong rồi Ai <= Ai+1.
Dòng thứ ba chứa số q (1 <= q <= 105) - số lượng yêu cầu.
Q dòng tiếp theo, mỗi dòng chứa hai số - ti (1 <= ti <= 4) và ki (1 < ;= ki <= 109).

Đầu ra:
In ra q dòng, số thứ i - đáp án của câu hỏi thứ i.

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
4
3 5 5 7
4
15
27
3 2
4 4		 5
-1
-1
3
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!