中小企业网站官网,六安网站优化,wordpress 目录菜单,服装设计培训班P8686 [蓝桥杯 2019 省 A] 修改数组--并查集 题目 并查集解析代码【并查集解】 Set 解法解析lower_bound代码 题目 并查集解析
首先先让所有的f#xff08;i#xff09;i#xff0c;即每个人最开始的祖先都是自己#xff0c;然后就每一次都让轮到那个数的父亲1#xff08… P8686 [蓝桥杯 2019 省 A] 修改数组--并查集 题目 并查集解析代码【并查集解】 Set 解法解析lower_bound代码 题目 并查集解析
首先先让所有的fii即每个人最开始的祖先都是自己然后就每一次都让轮到那个数的父亲1用过后的标记第二次出现的时候就直接用父亲替换掉
并查集的作用并查集用于快速查找元素的根节点并进行路径压缩以提高效率。
并查集适用场景
1.快速合并与查询需要频繁合并集合如标记某个数已被占用和查询根节点找下一个可用位置。 2.路径压缩优化通过压缩查找路径使得后续查询接近常数时间复杂度。 3.动态维护连续区间每个数字的父节点指向下一个可用位置天然维护了一个动态递增的区间。
代码【并查集解】
#include iostream
#include vector
#include set
#include cstring
#include algorithm
#include math.h
#include queue
#include climits // 包含INT_MAX常量
#include cctype
using namespace std;
int n, f[100010];int find(int x) {if (f[x] x)return x;return f[x] find(f[x]);
}int main() {cin n;for (int i 1; i 1e5; i)f[i] i;for (int i 0; i n; i) {int x;cin x;x find(x);cout x ;f[x] 1;//为下一次重复做准备}return 0;
}Set 解法解析
这道题我们可以利用set 的有序性和高效查找特性直接找到每个元素的最小可用值。
代码思路 先将1~1e6的值依次存入set中然后利用lower_bound()找到第一个大于等于x的值使用过后再利用erase()删除 【这个代码的思路完全符合我们脑中所想】
lower_bound
是一个用于在有序序列中【有序序列set】查找特定元素的函数。它返回指向第一个不小于给定值的元素的迭代器。结合set有序集合可以高效解决需要动态维护有序数据并快速查找的问题。
lower_bound 的核心功能 1.作用在有序序列中找到第一个不小于目标值的位置。 2.返回值 i 如果存在符合条件的元素返回指向该元素的迭代器。 ii如果所有元素都小于目标值返回容器的end()迭代器。
在 set 中使用 lower_bound set 的特性 1.元素唯一且按升序自动排序。 2.插入、删除和查找操作的时间复杂度为 O(log N)。 调用方式
auto it s.lower_bound(x); // it 是迭代器指向第一个 x 的元素
cout *it; // *it 是该元素的实际值
s.erase(it); // 直接传递迭代器删除元素不需要 *lower_bound 下界 upper_bound上界
为什么不用 vector 替代 set vector 的插入、删除和查找效率较低适合静态数据。
vector 的查找必须遍历或使用 find 算法效率低。
代码
#include iostream
#include vector
#include set
#include cstring
#include algorithm
#include math.h
#include queue
#include climits // 包含INT_MAX常量
#include cctype
using namespace std;
int n;
setint s;int main() {cin n;for (int i 1; i 1e6; i)s.insert(i);for (int i 0; i n; i) {int x;cin x;auto a s.lower_bound(x); //lower_bound返回第一个大于等于x的值在有序集合set中能完美解决该问题cout *a ;s.erase(a);}return 0;
}
