std::mutiset vs std::vector。在一个代码中获取 TLE，在另一个代码中获取 AC

Question

问题Link：https://cses.fi/problemset/task/1091/

我假设存在某种与时间复杂度相关的问题，但我无法确定我在这里做错了什么。

在此代码中获取超过时间限制的判决：

#include<bits/stdc++.h>
using namespace std;
#define int long long int
main()
{
    int n,m;
    scanf("%lld %lld",&n,&m);
    vector<int>tickets;
    for(int i=0; i<n; i++)
    {
        int x;
        scanf("%lld",&x);
        tickets.push_back(x);
    }
    sort(tickets.begin(),tickets.end());
    for(int i=0; i<m; i++)
    {
        int x;
        scanf("%lld",&x);
        auto index=lower_bound(tickets.begin(),tickets.end(),x);
        if(index==tickets.begin() and (*index>x or index==tickets.end()))
            printf("-1\n");
        else
        {
            if(*index!=x)
                index--;
            printf("%lld\n",*index);
            tickets.erase(index);
        }
    }
}

在此代码中获得接受的判决：

#include<bits/stdc++.h>
using namespace std;
#define int long long int
main()
{
    int n,m;
    scanf("%lld %lld",&n,&m);
    multiset<int>tickets;
    for(int i=0; i<n; i++)
    {
        int x;
        scanf("%lld",&x);
        tickets.insert(x);
    }
    for(int i=0; i<m; i++)
    {
        int x;
        scanf("%lld",&x);
        auto index=tickets.lower_bound(x);
        if(index==tickets.begin() and (*index>x or index==tickets.end()))
            printf("-1\n");
        else
        {
            if(*index!=x)
                index--;
            printf("%lld\n",*index);
            tickets.erase(index);
        }
    }
}

不明白为什么会这样。

Answer 1

这是因为您正在使用 tickets.erase(index) 语句。

在向量中（无论是否排序），erase() 是 O(n) 而对于多重集 erase() 通常是 O(logn)。

因此，当您使用向量然后在大小为 m 的 for 循环中使用 erase() 时，对于 i 的每次迭代都会得到额外的 O(n)因此，
O(nlogn (sorting) + m * (logn (lower_bound) + n (erase))) = O(m*n) 的总复杂度太多了。

但是对于多重集，使用 erase() 可以为每次迭代带来额外的 O(logn)，从而导致总时间复杂度为
O(nlogn (insert into multiset) + m * (logn (lower_bound) + logn (erase)) = O((m + n)logn).

我希望它能消除你的疑虑。阅读以下链接以更好地理解。
vector erase time complexity
multiset erase time complexity

std::mutiset vs std::vector。在一个代码中获取 TLE，在另一个代码中获取 AC

std::mutiset vs std::vector.Getting TLE in one code but AC in another

c++

sorting

binary-search

time-complexity

multiset