Problem

2/6

limite_inférieure/limite_supérieure

Theory Click to read/hide

lower_bound et upper_bound sont des fonctions de recherche binaires intégrées.

lower_bound - une fonction qui, en temps logarithmique, trouve le plus petit élément dans un tableau trié qui est supérieur ou égal à la valeur donnée k.
Il prend les bornes du tableau et la valeur de k comme arguments.
Renvoie un itérateur à l'élément trouvé, ou à la fin (non incluse) du tableau si aucun élément de ce type n'existe.
Vous pouvez en savoir plus dans la documentation.

upper_bound - une fonction qui, en temps logarithmique dans un tableau trié, trouve le plus petit élément strictement supérieur à la valeur donnée k.
Il prend les bornes du tableau et la valeur de k comme arguments.
Renvoie un itérateur à l'élément trouvé, ou à la fin (non incluse) du tableau si aucun élément de ce type n'existe.
Vous pouvez en savoir plus dans la documentation.

Il convient de préciser que l'utilisation de ces fonctions sur un ensemble ou un multiensemble ne fonctionne pas en temps logarithmique en raison du manque d'itérateurs dans les collections à accès aléatoire ci-dessus.
Cependant, ces collections ont des méthodes intégrées correspondantes (c'est-à-dire que vous devez les utiliser "à travers un point").

Exemples :
  vecteur a = { 0, 1, 3, 5, 7 } ; vector::iterator it ; it = borne_inférieure(a.begin(), a.end(), 4); // *il == 5 it = borne_inférieure(a.begin(), a.end(), 5); // *il == 5 it = borne_inférieure(a.begin(), a.end(), 8); // it == a.end() it = upper_bound(a.begin(), a.end(), 4); // *il == 5 it = upper_bound(a.begin(), a.end(), 5); // *il == 7 it = upper_bound(a.begin(), a.end(), -1); // *il == 0 // en soustrayant les itérateurs, vous pouvez obtenir l'index de l'élément trouvé int ind = borne_inférieure(a.begin(), a.end(), 4) - a.begin(); // ind == 3 // besoin d'utiliser des méthodes au lieu de fonctions pour les collections set et similaires set s{ 1, 3, 5 } ; set::iterator sit; sit = s.lower_bound(3); // *assis == 3 sit = s.upper_bound(3); // *assis == 5  

Problem

On vous donne un tableau ordonné A de n nombres naturels. 
Il y a q requêtes à traiter. Chaque requête reçoit deux paramètres - son type ti et le nombre ki.

Description des requêtes par leur type :
1) Trouver dans A le nombre minimum qui n'est pas inférieur à ki.
2) Trouver le nombre minimum dans A strictement supérieur à ki.
3) Trouver dans A le nombre maximum qui n'est pas supérieur à ki.
4) Trouver le nombre maximum dans A strictement inférieur à ki.

Pour chaque requête, indiquez le nombre trouvé, ou -1 s'il n'en existe pas.

Saisie :
La première ligne contient le nombre n (1 <= n <= 105) - le nombre d'éléments du tableau A.
La deuxième ligne contient n nombres naturels Ai (1 <= Ai <= 109) - les éléments du tableau eux-mêmes. De plus, pour tous je < n fait Ai <= Ai+1.
La troisième ligne contient le nombre q (1 <= q <= 105) - le nombre de requêtes.
Les q lignes suivantes contiennent chacune deux nombres - ti (1 <= ti <= 4) et ki (1 < ;= ki <= 109).

Sortie :
Imprimer q lignes, i-ème un nombre - la réponse à la i-ème requête.

Exemples :
 
Entrée Sortie
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!