C/C++

Задача на с++

Upper bound
На вход подаются N
целых чисел, а также набор из M
запросов, каждый из которых — целое число. Ваша задача — для каждого запроса найти количество чисел из исходного набора, меньших либо равных заданному в запросе числу. Использовать встроенные функции бинарного поиска запрещено.

Входные данные

Первая строка содержит число N
— количество элементов в массиве. (1⩽N⩽250000)
.
Вторая строка содержит N
целых чисел Ai
через пробел. (−109⩽Ai⩽109)
.
Третья строка содержит число M
— количество запросов. (1⩽M⩽250000)
.
Четвёртая строка содержит M
целых чисел Qi
через пробел. (−109⩽Qi⩽109)
.

Выходные данные

Выведите единственную строку с M
целыми числами — количествами чисел исходного массива, меньших либо равных соответствующему запросу.
ВВОД:
5
1 5 3 2 1
2
4 3
ВЫВОД:
4 4
М*
Макс **********
77
Пример кода:
 #include  

#include  

#include  

using namespace std; 

 

int main() { 

    int n, m; 

    cin >> n; 

    vector a(n); 

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

        cin >> a[i]; 

    } 

    sort(a.begin(), a.end()); 

    cin >> m; 

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

        int q; 

        cin >> q; 

        auto it = upper_bound(a.begin(), a.end(), q); 

        cout
Коля .
Коля .
25 860
Лучший ответ 
 #include  

#include  

using namespace std; 

int main() { 

    size_t n; 

    cin >> n; 

    vector a(n); 

    for (auto& x : a) cin >> x; 

    size_t m; 

    cin >> m; 

    vector q(m); 

    for (auto& x : q) cin >> x; 

    vector box(m); 

    for (auto& s : box) { 

        for (auto x : q) { 

            size_t k = 0; 

            for (auto t : a) if (t
ВШ
Владимир Шитов
68 238
Андрей Спиридонов Задачу этот код не решает (вместо вывода кол-ва чисел, не превосходящих q[m], выводит сумму по всем q[m]), но на N = 50000 работает раз в 10 быстрее, чем мой. Несмотря на 3 вложенных цикла...
Так и думал, что вставка в массив производительность убьёт. Надо было мне через деревья делать...
Андрей Спиридонов Хотя, нет, если ещё и M=100 зарядить, то мой в 3 раза быстрее отработает, а при M=1000 у меня 1.61 с, а у вас - Runtime Exceeded... Против асимптотики не попрёшь.

Но автору, похоже, по барабану. Он лайкнул ответ от нейросети, где используется "запрещённый" бинарный поиск из STL. Нейросеть не читает условий.
Орынбек Нурлан Ощутите всю мощь искусственного интеллекта! Он выше начальных условий и правил)
Встроенные запрещены - так напиши свою функцию бинарного поиска. Читал алгоритмы-то?

Вот так, например:
 #include 



using namespace std;



unsigned inspoint(const long *a, const unsigned len, const long v) {

    unsigned lo = 0, hi = len - 1;

    if (a[hi] == v) return hi;

    if (a[hi] < v) return len;

    while (lo + 1 < hi) {

        const unsigned med = (lo + hi) / 2;

        (a[med] > n;

    long *a = new long[n];

    cin >> a[0];

    for (unsigned i = 1; i < n; i++) {

        long v;

        cin >> v;

        unsigned ip = inspoint(a, i, v);

        for (unsigned j = i; j > ip; j--) {

            a[j] = a[j - 1];

        }

        a[ip] = v;

    }

    unsigned m;

    cin >> m;

    const char *sep = "";

    while (m--) {

        long q;

        cin >> q;

        unsigned ip = inspoint(a, n, q);

        cout
Omer Kanat
Omer Kanat
54 053
Omer Kanat Хотя, там ошибка в поиске точной границы, если есть одинаковые элементы. Лучше так (часть 1):
 #include 



using namespace std;



unsigned inspoint(const long *a, const unsigned len, const long v) {

    unsigned lo = 0, hi = len - 1;

    if (a[hi] < v) return len;

    while (lo < hi) {

        const unsigned med = (lo + hi) / 2;

        const bool less = a[med] < v;

        (less ? lo : hi) = med + less;

    }

    return lo;

}
Omer Kanat Часть 2:
 int main() {

    unsigned n;

    cin >> n;

    long *a = new long[n];

    cin >> a[0];

    for (unsigned i = 1; i < n; i++) {

        long v;

        cin >> v;

        unsigned ip = inspoint(a, i, v);

        for (unsigned j = i; j > ip; j--) {

            a[j] = a[j - 1];

        }

        a[ip] = v;

    }

    unsigned m;

    cin >> m;

    const char *sep = "";

    while (m--) {

        long q;

        cin >> q;

        unsigned ip = inspoint(a, n, q + 1);

        cout

Похожие вопросы