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 = lower_bound(a.begin(), a.end(), 4); // *它== 5 it = lower_bound(a.begin(), a.end(), 5); // *它== 5 it = lower_bound(a.begin(), a.end(), 8); // 它 == 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(); // 工业 == 3 // 需要对集合和类似集合使用方法而不是函数 设置 s{ 1, 3, 5 }; 设置::迭代器坐下； 坐 = s.lower_bound(3); // *坐 == 3 坐 = s.upper_bound(3); // *坐 == 5  

Problem

给定一个由 n 个自然数组成的有序数组 A。 
有 q 个请求要处理。每个查询都有两个参数 - 它的类型 ti 和数量 ki。

查询类型说明：
1) 在A中找出不小于ki的最小数。
2) 找出A中严格大于ki的最小数。
3) 在A中找出不大于ki的最大数。
4) 找出A中严格小于ki的最大数。

对于每个查询，报告找到的数字，如果不存在则返回 -1。

输入：
第一行包含数字 n (1 <= n <= 105) - 数组 A 的元素数。
第二行包含 n 个自然数 Ai (1 <= Ai <= 109) - 数组元素本身。此外，对于所有 i < n 完成 Ai <= Ai+1.
第三行包含数字 q (1 <= q <= 105) - 请求数。
接下来的 q 行每行包含两个数字 - ti (1 <= ti <= 4) 和 ki (1 < ;= ki <= 109).

输出：
打印 q 行，第 i 个数字 - 第 i 个查询的答案。

示例：
  <正文>

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!