600B |代码部队 |查询小于或等于元素

Question

问题如下：Link

我的代码如下：

#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()) << " ";

有没有不用内部函数就可以成功提交这个问题的方法？二分查找可以更优化吗？

Answer 1

这里，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)。

600B |代码部队 |查询小于或等于元素

600B | Codeforces | Queries about less or equal elements

algorithm

binary-search