600B | Codeforces | Запросы о меньшем или равном количестве элементов - PullRequest
Новая
       19

600B | Codeforces | Запросы о меньшем или равном количестве элементов

0 голосов
/ 26 мая 2020

Вот вопрос: Ссылка

Мой код ниже: 

#include <bits/stdc++.h>

using namespace std;
#define output(x) cout << x << endl
#define ll long long

ll binarySearch(vector<ll> vec, ll num, ll n) {
    ll left = 0;
    ll right = n-1;
    ll mid = 0;

    while (left <= right) {
        mid = (left+right)/2;

        if (left == right) {
            break;
        }

        if (vec[mid] <= num) {
            left = mid+1;
        }
        else {
            right = mid;
        }
    }

    if (vec[mid] <= num) {
        return mid+1;
    }

    return mid;
}

int main(int argc, char const *argv[])
{ 
    ios_base::sync_with_stdio(false);
    ll a, b;
    cin >> a >> b;
    vector<ll> avec(a);

    for (auto &it: avec) {
        cin >> it;
    }

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

    ll curr;
    map<ll, ll> answers;

    while (b--) {
        cin >> curr;

        if (answers[curr] != 0) {
            cout << answers[curr] << " ";
        }
        else {
            ll ans = binarySearch(avec, curr, a);
            answers[curr] = ans;

            cout << ans << " "; 
        }

    }

    cout << "\n";
    return 0;
}

Это не превышает временных ограничений. Однако, когда я использую внутреннюю функцию upper_bound вместо вызова моего binarySearch, она передает upper_bound, как показано ниже 

cout << (upper_bound(avec.begin(), avec.end(), curr) - avec.begin()) << " ";

Есть ли способ успешно отправить этот вопрос без необходимости использовать внутренняя функция? Можно ли более оптимизировать бинарный поиск?

1 Ответ

2 голосов
/ 27 мая 2020

Здесь, ll binarySearch(vector<ll> vec, ll num, ll n) {, вы передаете вектор vec копией.

Сложность копии O (n). Таким образом, даже если алгоритм равен O (logn), глобальная сложность функции все равно будет O (n).

Сделав вызов по ссылке: 

ll binarySearch(vector<ll> &vec, ll num, ll n) {

Вызов сама стоит O (1), а общая сложность функции остается O (logn).

...