2023蓝桥杯省赛B组「整数删除」题解（洛谷P12085） 双向链表+优先队列优化思路与代码解析

一、题目解读

    2023年蓝桥杯省赛B组「整数删除」问题（对应洛谷P12085）要求处理一个包含N个整数的序列，每次删除当前最小值，并将其左右相邻元素值相加，重复K次后输出剩余序列。题目难点在于高效维护动态最小值及节点间的邻接关系，涉及数据结构的选择与操作优化。

二、解题思路

采用“双向链表+优先队列（set）”的组合策略：

    1. 双向链表：通过自定义Node结构记录每个节点的值、前驱与后继指针，方便O(1)时间删除节点并更新邻接关系；

    2. 优先队列（set）：利用set自动维护元素值升序（同时考虑值相同情况下按原位置排序），确保每次删除的都是当前最小值；

    3. 值合并逻辑：删除节点时，将其值累加到左右相邻节点，并更新set中对应元素的新值，保证队列动态正确性。

三、解题步骤

1. 初始化

    构建N+2个节点的环形双向链表（头尾哨兵节点简化边界处理）；

    将每个节点值及位置插入set作为初始最小堆。

2. 循环删除K次

    每次从set中取出最小值节点（值+位置）；

    删除该节点，合并其值到左右邻居；

    更新邻居节点的新值，并重新插入set；

    标记已删除节点。

3. 输出结果

    遍历链表输出未被删除的节点值。

四、代码与注释

#include <iostream>
#include <vector>
#include <queue>
#include <set>
using namespace std;

// 定义节点结构（值+前后指针）
struct Node {
    long long value;   // 节点值
    int prev, next;    // 前驱/后继指针
    bool operator<(const Node& other) const {   // 排序规则：值优先，值相同按原位置排序
        return value < other.value || (value == other.value && prev < other.prev);
    }
};

int main() {
    ios::sync_with_stdio(false);   // 加快IO速度
    cin.tie(nullptr);
    
    int N, K;
    cin >> N >> K;   // 输入序列长度与删除次数
    
    // 构建双向链表
    vector<Node> nodes(N+2);
    set<pair<long long, int>> min_heap;   // 优先队列，存储值+位置对
    for (int i = 1; i <= N; ++i) {
        cin >> nodes[i].value;   // 读入节点值
        nodes[i].prev = i-1;     // 初始化指针
        nodes[i].next = i+1;
        min_heap.insert({nodes[i].value, i});   // 插入初始值
    }
    // 哨兵节点处理边界
    nodes[0].next = 1;
    nodes[N+1].prev = N;
    
    vector<bool> deleted(N+2, false);   // 标记删除状态
    
    // 核心循环：删除K次
    while (K--) {
        auto it = min_heap.begin();   // 获取当前最小值（值+位置）
        long long val = it->first;
        int pos = it->second;
        min_heap.erase(it);   // 从队列删除该节点
        
        // 合并到前驱节点
        int prev_pos = nodes[pos].prev;
        if (prev_pos!= 0) {
            min_heap.erase({nodes[prev_pos].value, prev_pos});   // 删除旧值
            nodes[prev_pos].value += val;   // 累加值
            min_heap.insert({nodes[prev_pos].value, prev_pos});   // 插入新值
        }
        
        // 合并到后继节点
        int next_pos = nodes[pos].next;
        if (next_pos!= N+1) {
            min_heap.erase({nodes[next_pos].value, next_pos});
            nodes[next_pos].value += val;
            min_heap.insert({nodes[next_pos].value, next_pos});
        }
        
        // 更新链表结构
        nodes[prev_pos].next = next_pos;
        nodes[next_pos].prev = prev_pos;
        deleted[pos] = true;   // 标记删除
    }
    
    // 输出剩余序列
    int current = nodes[0].next;
    while (current!= N+1) {
        cout << nodes[current].value << " ";
        current = nodes[current].next;
    }
    
    return 0;
}

五、总结

本解法通过双向链表降低删除操作的复杂度，利用优先队列维护动态最小值，避免全局扫描。关键在于节点删除时同步更新邻居节点值及set中的优先级，实现单次操作O(logN)效率。算法核心在于数据结构的巧妙组合与状态同步的精准处理，对算法竞赛中“动态维护+局部更新”类问题具有借鉴意义。