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 }; ベクトル::反復子それ; 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 // セットや同様のコレクションには関数の代わりにメソッドを使用する必要があります set s{ 1, 3, 5 }; set::iterator sit; 座る = s. lower_bound(3); // *座る == 3 座る = s.upper_bound(3); // *座る == 5  

Problem

n 個の自然数の順序付き配列 A が与えられます。 
処理するリクエストが q 個あります。各クエリには、型 ti と数値 ki の 2 つのパラメータが与えられます。

タイプ別のクエリの説明:
1) A から ki 以上の最小数を見つけます。
2) ki より厳密に大きい A の最小数を見つけます。
3) A で ki を超えない最大数を見つけます。
4) 厳密に ki より小さい A の最大数を見つけます。

クエリごとに、見つかった数を報告するか、存在しない場合は -1 を報告します。

入力:
最初の行には、数値 n (1 <= n <= 105) - 配列 A の要素数が含まれています。
2 行目には n 個の自然数 Ai (1 <= Ai <= 109) が含まれています - 配列要素そのものです。さらに、すべての i <> に対して、 n done Ai <= Ai+1.
3 行目には、数字 q (1 <= q <= 105) - リクエスト数が含まれます。
次の q 行には、それぞれ 2 つの数字が含まれます - ti (1 <= ti <= 4) と ki (1 <= ti <= 4) ;= 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!