0

Есть задача:

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

Пример:
Ввод:
5
1 5 3 2 1
2
4 3
Вывод:
4 3 Я написал такой код на Python:

def sort(a : list, x):
    L = -1
    R = len(a)
    while R - L > 1:
        M = (R + L) // 2
        if a[M] < x:
            L = M
        else:
            R = M
    return R

n = int(input())
a = sorted(list(map(int, input().split())))
m = int(input())
b = list(map(int, input().split()))
for q in b:
    r = sort(a, q)
    print(r)

Он работает отлично.
Вот тот же код на C++:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int count(vector<int> a, int x)
{
    int l = -1;
    int r = a.size();
    while (r - l > 1)
    {
        int m = (r + l) / 2;
        (a[m] < x ? l : r) = m;
    }
    return r;
}
int main()
{
    int n, m; cin >> n;
    vector<int> a (n);
    for (int i = 0; i < n; i++)
        cin >> a[i];
    sort(a.begin(), a.end());
    cin >> m;
    vector<int> b (m);
    for (int i = 0; i < m; i++)
        cin >> b[i];
    for (int q: b)
        cout << count(a, q) << " ";
}

Но он работает слишком медленно.
Прошу, помогите, как можно ускорить работу данного кода на С++?

2
  • 2
    count(vector<int> a - каждый вызов копирует вектор целиком. Сложность создания копии - линейная. На её фоне двоичный (за логарифм) поиск теряется. Commented 13 июл. 2022 в 7:13
  • Согласен с @Stanislav Volodarskiy. Всё, кроме копирования массива в функцию, вроде нормально. Просто передавайте массив в функцию по ссылке - измените объявление функции на int count(vector<int> &a, int x)
    – DmitryK
    Commented 13 июл. 2022 в 7:25

1 ответ 1

1

Нашёл ответ:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int count(vector<int> &a, int x)
{
    int l = -1;
    int r = a.size();
    while (r - l > 1)
    {
        int m = (r + l) / 2;
        (a[m] < x ? l : r) = m;
    }
    return r;
}
int main()
{
    int n, m; cin >> n;
    vector<int> a (n);
    for (int i = 0; i < n; i++)
        cin >> a[i];
    sort(a.begin(), a.end());
    cin >> m;
    vector<int> b (m);
    for (int i = 0; i < m; i++)
        cin >> b[i];
    for (int q: b)
        cout << count(a, q) << " ";
}
3
  • Вектор лучше передавать по константной ссылке, а еще лучше - std::span. Писать бинарный поиск самому хорошо для тренировки, но на деле лучше использовать (вы не поверите) std::lower_bound или std::partition_point. Commented 13 июл. 2022 в 8:43
  • @HolyBlackCat, в задании сказано "Использовать встроенные функции бинарного поиска запрещено.". Commented 13 июл. 2022 в 14:15
  • @StanislavVolodarskiy Угу, действительно. Не увидел. Commented 14 июл. 2022 в 6:06

Ваш ответ

Нажимая «Отправить ответ», вы соглашаетесь с условиями пользования и подтверждаете, что прочитали политику конфиденциальности.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.