2023年蓝桥杯省赛B组整数删除（洛谷P12085）：优先队列+双向链表解法

胡志明t

一、问题重述

给定N个整数的序列，进行K次操作：每次删除当前最小元素，并将其值加到相邻元素上。要求高效计算出最终序列。

二、完整代码解析（含详细注释）

1. #include <iostream>
   
2. #include <vector>
   
3. #include <queue>
   
4. #include <set>
   
5. using namespace std;
   
6. 
   
7. // 定义链表节点结构
   
8. struct Node {
   
9.     long long value;   // 存储节点值
   
10.     int prev, next;    // 前驱和后继指针
    
11.     // 重载运算符用于set排序
    
12.     bool operator<(const Node& other) const {
    
13.         return value < other.value || (value == other.value && prev < other.prev);
    
14.     }
    
15. };
    
16. 
    
17. int main() {
    
18.     ios::sync_with_stdio(false);  // 加速输入输出
    
19.     cin.tie(nullptr);
    
20.    
    
21.     int N, K;
    
22.     cin >> N >> K;  // 输入数字个数和操作次数
    
23.    
    
24.     // 初始化双向链表（含哨兵节点）
    
25.     vector<Node> nodes(N+2);  
    
26.     set<pair<long long, int>> min_heap;  // 使用set模拟最小堆
    
27.    
    
28.     // 构建初始链表和优先队列
    
29.     for (int i = 1; i <= N; ++i) {
    
30.         cin >> nodes[i].value;
    
31.         nodes[i].prev = i-1;
    
32.         nodes[i].next = i+1;
    
33.         min_heap.insert({nodes[i].value, i});  // 存入值和位置
    
34.     }
    
35.     // 设置哨兵节点
    
36.     nodes[0].next = 1;     // 头哨兵
    
37.     nodes[N+1].prev = N;   // 尾哨兵
    
38.    
    
39.     vector<bool> deleted(N+2, false);  // 标记删除状态
    
40.    
    
41.     // 执行K次删除操作
    
42.     while (K--) {
    
43.         auto it = min_heap.begin();  // 获取最小值
    
44.         long long val = it->first;
    
45.         int pos = it->second;
    
46.         min_heap.erase(it);
    
47.         
    
48.         // 处理前驱节点
    
49.         int prev_pos = nodes[pos].prev;
    
50.         if (prev_pos != 0) {  // 如果不是头节点
    
51.             min_heap.erase({nodes[prev_pos].value, prev_pos});
    
52.             nodes[prev_pos].value += val;  // 前驱节点增值
    
53.             min_heap.insert({nodes[prev_pos].value, prev_pos});
    
54.         }
    
55.         
    
56.         // 处理后继节点
    
57.         int next_pos = nodes[pos].next;
    
58.         if (next_pos != N+1) {  // 如果不是尾节点
    
59.             min_heap.erase({nodes[next_pos].value, next_pos});
    
60.             nodes[next_pos].value += val;  // 后继节点增值
    
61.             min_heap.insert({nodes[next_pos].value, next_pos});
    
62.         }
    
63.         
    
64.         // 更新链表指针
    
65.         nodes[prev_pos].next = next_pos;
    
66.         nodes[next_pos].prev = prev_pos;
    
67.         deleted[pos] = true;  // 标记删除
    
68.     }
    
69.    
    
70.     // 输出最终序列
    
71.     int current = nodes[0].next;  // 从**个有效节点开始
    
72.     while (current != N+1) {
    
73.         cout << nodes[current].value << " ";
    
74.         current = nodes[current].next;
    
75.     }
    
76.    
    
77.     return 0;
    
78. }

复制代码

三、核心算法解析

• 数据结构设计：
  
  
  • 双向链表维护元素间关系
  • set模拟最小堆实现高效取最小值
  • 哨兵节点简化边界条件处理
    
    
• 关键操作流程：
  
  
  • 每次取出最小值后更新相邻节点
  • 动态维护优先队列中的值
  • 通过标记数组避免重复处理
    
    
• 复杂度分析：
  
  
  • 时间复杂度：O(KlogN)（每次堆操作logN）
  • 空间复杂度：O(N)（存储链表和堆）
    
    

四、常见问题解答

Q：为什么用set而不用priority_queue？ A：set支持快速查找和删除任意元素，priority_queue只能访问堆顶

Q：如何处理相同最小值的冲突？ A：通过自定义比较函数，当值相同时按位置排序

Q：哨兵节点有什么作用？ A：统一处理头尾节点的边界情况，避免额外条件判断

来源：编程学习