Difference in two ways of using lower_bound [C++]std::set::lower_bound与std::lower_bound

glm233

发布于 2020-09-28 10:33:14

4910

发布于 2020-09-28 10:33:14

文章被收录于专栏：glm的全栈学习之路

缘起：Codeforces Round #555 (Div. 3), problem: (E) Minimum Array 这道题目难度不大，大概在div2 C题左右

但是有个关键点就是stl中lowerbound和set自带的lowerbound差别，

很naive的我想着这两个都是o（logn）的，事实上，t了无数发后才发现标程是 s.lower_bound(x)而我是(s.begin(),s.end(),x) 差别是我的是o（n），标程是logn级别的

set输入时已经建好树而模板lowerbound要多一个类似建树的过程

可以简单的记住 algorithm的是通用的的lower_bound算法 set的是专有的s.lower_bound(x)算法肯定set快一点

STL的设计是通用的和灵活的。

有很多容器，它们都需要支持通用操作，比如遍历元素、排序、查找元素等等。因此，STL并没有在所有容器中实现多个方法container.sort()，而是提供了一个统一的函数std::sort()，它可以用于对不同的容器进行排序，而不是在所有容器中实现多个方法container.sort()，其中大多数方法都使用相同的算法。函数std::lower_bound()也是如此。

然而，由于容器的内部模型，并不是所有的容器都使用相同的算法。例如，不能像在vector中那样以随机顺序访问list中的元素。对于这种情况，有专门为容器设计的方法。因此list有方法list::sort()，它使用特定于链表结构的算法。

set和lower_bound()也是一样。有一个统一的函数std::lower_bound()，它在随机访问迭代器上的O(logN)中工作，在其他迭代器上的O(N)中工作。容器std::set具有双向迭代器，不能提供对其成员的随机访问。所以统一的std::lower_bound()在O(N)中工作。而容器集是二叉搜索树，可以使用不同的算法在O(logN)中找到下界，具体针对std::set的内部结构。它在方法集::lower_bound()中实现，在O(logN)中工作。

附上AC代码

// luogu-judger-enable-o2
#include<bits/stdc++.h>
#include<unordered_set>
#define rg register ll
#define inf 2147483647
#define min(a,b) (a<b?a:b)
#define max(a,b) (a>b?a:b)
#define ll long long
#define maxn 200005
const double eps = 1e-8;
using namespace std;
inline ll read()
{
	char ch = getchar(); ll s = 0, w = 1;
	while (ch < 48 || ch>57) { if (ch == '-')w = -1; ch = getchar(); }
	while (ch >= 48 && ch <= 57) { s = (s << 1) + (s << 3) + (ch ^ 48); ch = getchar(); }
	return s * w;
}
inline void write(ll x)
{
	if (x < 0)putchar('-'), x = -x;
	if (x > 9)write(x / 10);
	putchar(x % 10 + 48);
}
ll n, a[maxn], ans[maxn], minn = maxn;
multiset<ll>p;
 
int main()
{
	n = read();
	for (rg i = 1; i <= n; i++)a[i] = read();
	for (rg i = 1; i <= n; i++)
	{
		ll x = read();
		minn = min(x, minn);
		p.insert(x);
	}
	for (rg i = 1; i <= n; i++)
	{
		ll temp = n - a[i];
		if (p.lower_bound(temp) == p.end())
		{
			ans[i] = (a[i] + *p.begin()) % n;
			p.erase(p.begin());
 
		}
		else
		{
			temp = *(p.lower_bound(temp));
			//cout << temp << endl;
				ans[i] = (a[i] + temp) % n;
				p.erase(p.lower_bound(temp));
				//cout << n-temp << " "<<p.size()<<endl;
		}
	}
	for (rg i = 1; i <= n; i++)
	{
		i == n ? cout << ans[i] : cout << ans[i] << " ";
	}
	return 0;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2019/08/02 ，如有侵权请联系 cloudcommunity@tencent.com 删除

容器