Problem

2/6

하한/상한

Theory Click to read/hide

lower_bound 및 upper_bound는 내장된 이진 검색 기능입니다.

lower_bound - 대수 시간에서 주어진 값 k보다 크거나 같은 정렬된 배열에서 가장 작은 요소를 찾는 함수입니다.
배열의 범위와 k 값을 인수로 사용합니다.
발견된 요소 또는 그러한 요소가 존재하지 않는 경우 배열의 끝(포함되지 않음)에 대한 반복자를 반환합니다.
문서에서 자세한 내용을 확인할 수 있습니다.

upper_bound - 정렬된 배열의 대수 시간에서 주어진 값 k보다 엄격하게 큰 가장 작은 요소를 찾는 함수입니다.
배열의 범위와 k 값을 인수로 사용합니다.
발견된 요소 또는 그러한 요소가 존재하지 않는 경우 배열의 끝(포함되지 않음)에 대한 반복자를 반환합니다.
문서에서 자세한 내용을 확인할 수 있습니다.

위의 랜덤 액세스 컬렉션에 반복자가 없기 때문에 집합 또는 다중 집합에서 이러한 함수를 사용하는 것이 대수 시간에 작동하지 않는다는 점을 명확히 할 가치가 있습니다.
그러나 이러한 컬렉션에는 해당 내장 메서드가 있습니다(즉, "점을 통해" 사용해야 함).

예:
  벡터 a = { 0, 1, 3, 5, 7 }; vector::iterator it; it = lower_bound(a.begin(), a.end(), 4); // *it == 5 it = lower_bound(a.begin(), a.end(), 5); // *it == 5 it = lower_bound(a.begin(), a.end(), 8); // 그것 == a.end() it = upper_bound(a.begin(), a.end(), 4); // *it == 5 it = upper_bound(a.begin(), a.end(), 5); // *it == 7 it = upper_bound(a.begin(), a.end(), -1); // *it == 0 // 반복자를 빼면 찾은 요소의 인덱스를 얻을 수 있습니다. int ind = lower_bound(a.begin(), a.end(), 4) - a.begin(); // 인더 == 3 // set 및 유사한 컬렉션에 대해 함수 대신 메서드를 사용해야 합니다. set s{ 1, 3, 5 }; set::iterator 앉아; 앉아 = s.lower_bound(3); // *앉아 == 3 앉아 = s.upper_bound(3); // *앉아 == 5  

Problem

n개의 자연수로 구성된 정렬된 배열 A가 제공됩니다. 
처리할 요청이 q개 있습니다. 각 쿼리에는 유형 ti와 숫자 ki의 두 가지 매개변수가 제공됩니다.

유형별 쿼리 설명:
1) A에서 ki보다 작지 않은 최소 수를 찾습니다.
2) ki보다 엄격하게 큰 A에서 최소 수를 찾습니다.
3) A에서 ki보다 크지 않은 최대 수를 찾습니다.
4) ki보다 엄격하게 작은 A에서 최대 수를 찾습니다.

각 검색어에 대해 찾은 수를 보고하거나, 없는 경우 -1을 보고합니다.

입력:
첫 번째 줄에는 배열 A의 요소 수인 n(1 <= n <= 105)이 포함됩니다.
두 번째 줄에는 배열 요소 자체인 n개의 자연수 Ai(1 <= Ai <= 109)가 포함됩니다. 더욱이, 모든 i < n 완료 Ai <= Ai+1.
세 번째 줄에는 숫자 q(1 <= q <= 105) - 요청 수를 포함합니다.
다음 q 행에는 각각 두 개의 숫자가 포함됩니다. ti (1 <= ti <= 4) 및 ki (1 < ;= ki <= 109).

출력:
i번째 쿼리에 대한 답인 i번째 숫자를 q줄로 인쇄합니다.

예:
  <몸>

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++
입력 출력
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!