trudbot

用户名：2185759039

访问量：936

签　名：

等　　级
排　　名	22952
经　　验	485
参赛次数	0
文章发表	4
年　　龄	0
在职情况	学生
学　　校
专　　业

　　自我简介：

TA的其他文章

树上差分
浏览：130

你可能喜欢

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

堆 + 双向链表

　　作者: trudbot　　　　发表时间：2023-04-09 16:14:51 浏览：469　|　评论：4　

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

## 试题H: 整数删除

### 题意描述

给定一个长度为N 的整数数列：$A_1,A_2...A_N$。

你要重复以下操作K 次：每次选择数列中最小的整数（如果最小值不止一个，选择最靠前的），将其删除。并把与它相邻的整数加上被删除的数值。

输出K 次操作后的序列。

### 双向链表 | 最小堆

由于要进行大量的删除操作, 不难想到可以使用链表.

而本题需要动态的求最小值, 显然可以使用堆.

每次从堆中取出最小值的下标, 然后在链表中删除它.

但本题特殊点在于`将其删除。并把与它相邻的整数加上被删除的数值`, 所以会导致还在堆中的元素的权的变化.

我们可以注意到, 每次删除操作只会让一些元素变大, 而不会让元素变小. 也就是, 可能会让原本的最小值变成不是最小值.

因此我们取出堆中的最小值时, 需要将此元素的排序权和实际的值进行对比, 如果实际的值变大了, 则当前元素并不一定是最小值, 需要重新放回堆中.

### 参考代码

每次删除操作最多会让两个元素的值变化, 因此从堆中取出的次数是k的线性, 时间复杂度为$O(n + k) \log n$

```cpp
//
// Created by trudbot on 2023/4/9.
//

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 5e5 + 10;
ll v[N], l[N], r[N];

//双向链表的删除操作， 删除x结点
void del(int x) {
    r[l[x]] = r[x], l[r[x]] = l[x];
    v[l[x]] += v[x], v[r[x]] += v[x];
}

int main () {
    int n, k; cin >> n >> k;
	//最小堆， 堆中的元素是{权值， 结点下标}
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> h;
	
	//输入并构造双向链表
	r[0] = 1, l[n + 1] = n;
    for (int i = 1; i <= n; i ++)
        cin >> v[i], l[i] = i - 1, r[i] = i + 1, h.push({v[i], i});
    while (k --) {
        auto p = h.top(); h.pop();
		//如果v发生变化， 则目前的元素不一定是最小值， 需要重新放入堆中
        if (p.first != v[p.second]) h.push({v[p.second], p.second}), k ++;
        else del(p.second);
    }
	//输出链表剩余的元素
    int head = r[0];
    while (head != n + 1) {
        cout << v[head]<< " ";
        head = r[head];
    }
    return 0;
}
```

0.0分

15 人评分

C语言网提供「C语言、C++、算法竞赛、真题百练、Python课程」在线课程，全部由资深研发工程师或ACM金牌大佬亲授课，更科学、全面的课程体系，以在线视频+在线评测的学习模式学习，学练同步，拒绝理论派，真正学会编程！还有奖学金等增值福利等你！

　　评论区

沉默雨巷

厉害，真厉害

2023-06-01 00:07:17 | |

雨落看闲人i

为什么我的代码类似只能有81分

2023-04-25 15:08:05 | |

s47rsl

有样例超时了

2023-04-11 16:33:37 | |

trudbot 2023-04-11 17:04:14 |

你好。文中代码是能过的。

s47rsl 2023-04-12 18:50:55 |

抱歉确实过了，但是我昨天16:32:36提交相同代码时也确实有一个超时，今天好了

s47rsl 2023-04-12 18:51:16 |

抱歉确实过了，但是我昨天16:32:36提交相同代码时也确实有一个超时，今天好了

s47rsl 2023-04-12 18:52:35 |

另外请问下您使用的是什么编译环境？

溯月

%%%%%

2023-04-11 08:16:39 | |

trudbot

TA的其他文章

你可能喜欢

母牛的故事（C语言代码）

C语言训练-8除不尽的数（C语言代码）

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

简单编码（C++代码）（这里推荐用switch）

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

堆 + 双向链表

评论区

精彩推荐

C语言训练-求矩阵的两对角线上的元素之和（C语言代码）

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

淘淘的名单（C语言代码）

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

蓝桥杯历届试题-翻硬币（C++代码）

剪刀石头布（C语言代码）

字符串比较（C语言代码）

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

JAM计数法（C语言代码）

C语言训练-字符串正反连接（C语言代码）

trudbot

TA的其他文章

你可能喜欢

母牛的故事 （C语言代码）

C语言训练-8除不尽的数 （C语言代码）

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

简单编码 （C++代码）（这里推荐用switch）

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

堆 + 双向链表

评论区

精彩推荐

C语言训练-求矩阵的两对角线上的元素之和 （C语言代码）

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

淘淘的名单 （C语言代码）

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

蓝桥杯历届试题-翻硬币 （C++代码）

剪刀石头布 （C语言代码）

字符串比较 （C语言代码）

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

JAM计数法 （C语言代码）

C语言训练-字符串正反连接 （C语言代码）

母牛的故事（C语言代码）

C语言训练-8除不尽的数（C语言代码）

简单编码（C++代码）（这里推荐用switch）

　　评论区

C语言训练-求矩阵的两对角线上的元素之和（C语言代码）

淘淘的名单（C语言代码）

蓝桥杯历届试题-翻硬币（C++代码）

剪刀石头布（C语言代码）

字符串比较（C语言代码）

JAM计数法（C语言代码）

C语言训练-字符串正反连接（C语言代码）