Question

C++!! Upper bound На вход подаются N целых чисел, а также набор из M запросов, каждый из которых — целое число. Ваша задача — для каждого запроса найти количество чисел из исходного набора, меньших либо равных заданному в запросе числу. Использовать встроенные функции бинарного поиска запрещено.Входные данныеПервая строка содержит число N — количество элементов в массиве. 1≤N≤250000.Вторая строка содержит N целых чисел Ai через пробел. −10^9≤Ai≤10^9.Третья строка содержит число M — количество запросов. 1≤M≤250000.Четвёртая строка содержит M целых чисел Qi через пробел. −10^9≤Qi≤10^9.Выходные данныеВыведите единственную строку с M целыми числами — количествами чисел исходного массива, меньших либо равных соответствующему запросу.ПримерыВвод51 5 3 2 124 3Вывод4 4ОграниченияВремя выполнения: 3 секунды

Answer 1

#include <iostream>

using namespace std;

int main() {

int N;

cin >> N;

long* arrN = new long[N];

for (int i = 0; i < N; ++i) {

 cin >> arrN[i];

}

int M;

cin >> M;

long* arrM = new long[M];

for (int i = 0; i < M; ++i) {

 cin >> arrM[i];

}

for (int i = 0; i < M; ++i) {

 int count = 0;

 for (int j = 0; j < N; ++j) {

  if (arrN[j] <= arrM[i]) {

   ++count;

  }

 }

 cout << count << " ";

}

}

Answer 2

Для решения этой задачи, где необходимо найти количество чисел в исходном наборе, меньших или равных каждому из запросов, можно воспользоваться алгоритмом поиска с использованием простого цикла. Вот C++ код, который выполняет это:

cppCopy code
#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    int N, M;
    std::cin >> N;

    std::vector<int> numbers(N);

    for (int i = 0; i < N; ++i) {
        std::cin >> numbers[i];
    }

    // Сортируем исходный массив, чтобы можно было быстро искать элементы.
    std::sort(numbers.begin(), numbers.end());

    std::cin >> M;
    std::vector<int> queries(M);

    for (int i = 0; i < M; ++i) {
        std::cin >> queries[i];
    }

    for (int i = 0; i < M; ++i) {
        // Используем std::upper_bound для поиска верхней границы (первого элемента, большего заданного числа)
        int count = std::upper_bound(numbers.begin(), numbers.end(), queries[i]) - numbers.begin();
        std::cout << count << " ";
    }

    return 0;
}

Этот код сначала считывает входные данные, затем сортирует исходный массив чисел. Для каждого запроса используется std::upper_bound, чтобы найти индекс первого числа, которое больше заданного числа, и затем выводит количество чисел, меньших или равных этому числу.