正在加载中...
multiset(cf-1862-round894-g)
multiset(cf-1862-round894-g)
void solve() |
数据结构
- std::multiset
s, d{0} :s
存储输入的整数,d
存储这些整数之间的差值。
算法描述
add 函数
add
函数接收一个整数 x
,将其加入到 s
中,并据此更新 d
。
- 插入:
auto it = s.insert(x);
- 找到相邻元素:
auto r = std::next(it);
- 更新差值集合 d: 基于
x
和它的前后元素(如果存在)更新d
。
特点
- 使用了
std::multiset::insert
来插入元素。 - 使用了
std::next
和std::prev
来找到相邻的元素。
del 函数
del
函数接收一个整数 x
,将其从 s
中删除,并据此更新 d
。
特点
- 使用了
std::multiset::find
和std::multiset::erase
来删除元素。 - 使用了
std::multiset::extract
来精确地删除d
中的元素。
STL 特性和函数
std::multiset
std::multiset
是一个排序的集合,允许存储重复元素。它通常用于需要快速查找、删除和插入操作的场合。
特定用法
s.insert(x)
: 插入元素。时间复杂度为 。s.find(x)
: 查找元素,返回一个指向元素的迭代器。如果元素不存在,则返回s.end()
。时间复杂度为 (O(\log n))。s.erase(it)
: 删除元素,接受一个迭代器作为参数。时间复杂度为 (O(1))。s.extract(x)
: 精确删除元素,与erase
不同的是,extract
不会使其他迭代器失效。时间复杂度为 (O(1))。
std::multiset 与 std::priority_queue 的比较
- 查找能力:
multiset
允许快速查找任何元素,而priority_queue
只能快速访问队列中的最大或最小元素。 - 删除操作:
multiset
可以删除任何特定元素,priority_queue
只能删除队列顶部的元素。 - 排序:
multiset
总是排序的,priority_queue
内部排序但对外表现为部分排序。 - 复杂度: 在
multiset
中插入、删除和查找操作通常具有 (O(\log n)) 的时间复杂度。priority_queue
的插入和删除操作也是 (O(\log n)),但查找(除了顶部元素)则可能需要 (O(n))。 - 迭代器失效: 使用
multiset
的extract
方法可以避免迭代器失效,这在某些算法中是一个非常有用的特性。priority_queue
没有这样的操作。
与 std::priority_queue
相比,std::multiset
提供了更多的灵活性和查找能力,特别是 std::multiset::extract
函数在算法中的应用具有重要意义。
本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 善良的xwysyy!