当我解决一个算法问题时,我的解决方案由于时间问题无法通过。
但我意识到通过的考试和我的考试之间的唯一区别是
bag.lower_bound(jewerly[i].first) != bag.end() //passed lower_bound(bag.begin(), bag.end(), jewerly[i].first) != bag.end() //failed
我已经用 clock()
检查过它,它显然比另一个慢。
这两个代码有什么区别?
#include <cstdio>
#include <set>
#include <algorithm>
using namespace std;
const int MAXN = 300100;
bool cmp(pair<int, int> a, pair<int, int> b)
{
if(a.second != b.second)
return a.second > b.second;
return a.first < b.first;
}
pair<int, int> jewerly[MAXN];
multiset<int> bag;
int main()
{
int N, K, M;
scanf("%d%d", &N, &K);
int w, p;
for(int i = 0; i<N; i++)
{
scanf("%d%d", &w, &p);
jewerly[i] = {w, p};
}
for(int i = 0; i<K; i++)
{
scanf("%d", &M);
bag.insert(M);
}
sort(jewerly, jewerly+N, cmp);
clock_t begin = clock();
long long sum = 0;
for(int i = 0; i<N; i++) // #1
{
if( bag.empty() ) break;
if( lower_bound(bag.begin(), bag.end(), jewerly[i].first) != bag.end())
{
sum += jewerly[i].second;
bag.erase(bag.lower_bound(jewerly[i].first));
}
}
/*
for(int i = 0; i<N; i++) //#2
{
if( bag.empty() ) break;
if( bag.lower_bound(jewerly[i].first) != bag.end())
{
sum += jewerly[i].second;
bag.erase(bag.lower_bound(jewerly[i].first));
}
}
*/
clock_t end = clock();
printf("%lf\n", double(end-begin));
}
Test Input 10 8 1 65 5 23 1 30 9 40 3 50 2 90 5 30 5 30 7 80 2 99 10 15 12 5 3 5 2 2
最佳答案
std::lower_bound
无法访问 std::multiset
的内部结构。它不是 O(log N),因为 std::multiset
的迭代器不是随机访问的(并且您不可能比在 Theta(N) 中更快地实现非随机访问迭代器)
std::multiset::lower_bound
确实可以访问树的结构并且可以很容易地实现复杂度 O(tree height) 也就是 O(log N)
关于algorithm - 为什么两个看似 lower_bound() 相同的方法有不同的处理时间,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/34922113/