2361788963

用户名：2361788963

访问量：2302

签　名：

等　　级
排　　名	8416
经　　验	1181
参赛次数	0
文章发表	16
年　　龄	0
在职情况	学生
学　　校	广州软件学院
专　　业

　　自我简介：

TA的其他文章

一维迭代解法
浏览：26

贡献值解法
浏览：82

简洁暴力的dfs就可以了
浏览：25

你可能喜欢

A+B for Input-Output Practice (IV) （C++代码）

2005年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

并查集与路径压缩

　　作者: 2361788963　　　　发表时间：2023-04-10 19:47:58 浏览：347　|　评论：1　

原题链接：蓝桥杯2023年第十四届省赛真题-整数删除

利用并查集的路径压缩，快速找到最左和最右的可用节点
```cpp
#include<bits/stdc++.h>
using namespace std;
#define pr pair<ll,int>
#define ll long long
const int N = 5e5 + 5;
ll L[N], R[N], V[N], n, k;
priority_queue<pr, vector<pr>, greater<pr>> que;
int findR(int x) {
	if (R[x] == x) return x;
	return R[x] = findR(R[x]);
}
int findL(int x) {
	if (L[x] == x) return x;
	return L[x] = findL(L[x]);
}
void mergeL(int l, int x) {
	L[x] = findL(l);
}
void mergeR(int r, int x) {
	R[x] = findR(r);
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> n >> k;
	for (int i = 1; i <= n; i++) {
		cin >> V[i];
		que.push({ V[i],i });
		//初始化根节点为自己
		L[i] = i;
		R[i] = i;
	}
	while (k--) {
		auto p = que.top(); que.pop();
		ll pv = p.first, pi = p.second;
		//如果优先队列的值不等于合并后数组里的值，说明改动过，需重新加入队列
		while (pv != V[pi]) {
			que.push({ V[pi] ,pi });
			p = que.top(); que.pop();
			pv = p.first; pi = p.second;
		};
		
		//查询最左和最右，并将本节点添加到最左和最右的查询集合，超出范围会查询到0，但不影响1到n的结果
		int l = findL(pi - 1), r = findR(pi + 1);
		V[l] += V[pi];V[r] += V[pi];
		mergeL(l, pi);mergeR(r, pi);
	}
	for (int i = 1; i <= n; i++) {
		if (L[i] == i) cout << V[i] << " ";
	}
	return 0;
}
```

0.0分

5 人评分

看不懂代码？想转换其他语言的代码？或者想问其他问题？试试问问AI编程助手，随时响应你的问题：

编程语言转换

万能编程问答

代码解释器

代码纠错

SQL生成与解释

　　评论区

s47rsl

dalao用的什么编译环境啊

2023-04-11 16:47:45

2361788963

TA的其他文章

你可能喜欢

弟弟的作业（C语言代码）

A+B for Input-Output Practice (IV) （C++代码）

2005年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

简洁的代码

点我有惊喜！你懂得！

并查集与路径压缩

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题8.4 （C语言代码）

矩阵转置（C语言代码）

回文数(一) （C语言代码）

C语言程序设计教程（第三版）课后习题5.8 （C语言代码）

C语言程序设计教程（第三版）课后习题6.6 （C语言代码）

用筛法求之N内的素数。（C++代码）

简单的a+b （C语言代码）

2003年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

C二级辅导-进制转换（C语言代码）

简单的事情（C语言代码）

2361788963

TA的其他文章

你可能喜欢

弟弟的作业 （C语言代码）

A+B for Input-Output Practice (IV) （C++代码）

2005年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

简洁的代码

点我有惊喜！你懂得！

并查集与路径压缩

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题8.4 （C语言代码）

矩阵转置 （C语言代码）

回文数(一) （C语言代码）

C语言程序设计教程（第三版）课后习题5.8 （C语言代码）

C语言程序设计教程（第三版）课后习题6.6 （C语言代码）

用筛法求之N内的素数。 （C++代码）

简单的a+b （C语言代码）

2003年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

C二级辅导-进制转换 （C语言代码）

简单的事情 （C语言代码）

弟弟的作业（C语言代码）

　　评论区

矩阵转置（C语言代码）

用筛法求之N内的素数。（C++代码）

C二级辅导-进制转换（C语言代码）

简单的事情（C语言代码）