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

6小时前比赛题解18

一、问题重述

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

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

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

// 定义链表节点结构
struct Node {
    long long value;   // 存储节点值
    int prev, next;    // 前驱和后继指针
    // 重载运算符用于set排序
    bool operator<(const Node& other) const {
        return value < other.value || (value == other.value && prev < other.prev);
    }
};

int main() {
    ios::sync_with_stdio(false);  // 加速输入输出
    cin.tie(nullptr);
    
    int N, K;
    cin >> N >> K;  // 输入数字个数和操作次数
    
    // 初始化双向链表（含哨兵节点）
    vector<Node> nodes(N+2);  
    set<pair<long long, int>> min_heap;  // 使用set模拟最小堆
    
    // 构建初始链表和优先队列
    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;
}