4961. 整数删除

$WA 代码$

#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;

vector<LL> v;
int n, k, tmp;

int main(){
    scanf("%d%d", &n, &k);
    for(int i = 0; i < n; i ++ ){
        scanf("%d", &tmp);
        v.push_back(tmp);
    }
    while(k -- ){
        // 初始化最小值为第一个元素
        LL m = v[0];
        int ind = 0;
        // 从前往后寻找最小值
        for(int i = 1; i < v.size(); i ++ )
            if(v[i] < m){
                m = v[i];
                ind = i;
            }
        // 如果最小值不是第一个元素，更新前一个元素
        if(ind > 0) v[ind - 1] += m;
        // 如果最小值不是最后一个元素，更新后一个元素
        if(ind < v.size() - 1) v[ind + 1] += m;
        // 删除元素
        v.erase(v.begin() + ind);
    }
    for(int i = 0; i < v.size(); i ++ ) printf("%lld ", v[i]);
    return 0;
}

针对这个问题，正确的解决方案需要我们在每一次操作中确保可以有效地找到最小的元素，并且在移除这个元素后，正确地更新与其相邻元素的值。我们可以使用一个优先队列来帮助我们高效地找到最小的元素，但是我们需要一种方式来确保当一个元素的值被更新时，这个更新能够反映在未来的操作中。这意味着我们需要一种机制来跟踪每个元素是否被更新过，并且确保只有当前最小且未被处理的元素会被操作。

为了实现这一点，我们可以采用以下策略：

使用一个优先队列来存储所有元素及其索引，确保我们可以高效地找到最小的元素。
使用一个数组来跟踪每个元素的当前值，以便在删除元素后更新相邻元素的值。
使用一个布尔数组来标记哪些元素已经被删除，以避免在后续操作中重复处理它们。
然而，简单地更新相邻元素的值并重新将它们插入优先队列可能会导致一些元素被错误地多次更新。为了避免这个问题，我们实际上需要在找到最小元素并决定删除它之前，就计算好并更新相邻元素的值。但在这个过程中，优先队列中的元素顺序可能会因为元素值的更新而需要调整，这是标准的优先队列不支持的操作。

考虑到这些限制，我们采用的策略需要确保：

在每次操作中，我们都重新计算和更新了所有元素的正确状态，包括它们的值和是否被删除的标记。
更新操作应该尽可能高效，避免对整个数组进行全扫描。
但是，基于优先队列和上述方法的直接实现可能会导致时间复杂度过高，因此，这个问题实际上更适合使用一种称为“延迟删除”（lazy deletion）的技术，或者使用一个额外的数据结构来动态地管理和更新元素的状态，同时保持高效的元素查找和删除操作。

这种问题的一个更实际和简洁的解决方案可能涉及到使用一个排序的数据结构（如平衡二叉搜索树），但是在C++标准库中没有直接可用的结构可以同时高效地支持按值查找最小元素、删除元素、和更新元素值的操作。因此，真正高效的实现可能会相当复杂，并且需要使用到更高级的数据结构，如树状数组（Fenwick Tree）或线段树（Segment Tree），这些都超出了简单解决方案的范畴。

鉴于这些考虑，我之前的建议尝试提供了一个方向，但没有充分解决所有这些挑战。正确实现这种类型的操作要求深入了解高级数据结构和算法，并且实现的复杂度可能远远超过简单优先队列的使用范围。
因此不妨寻找更具体的数据结构或算法，专门针对动态数据操作进行优化，如使用树状数组（Fenwick Tree）、线段树（Segment Tree），或者是平衡二叉搜索树（如AVL树、红黑树）等。然而，对于这个具体问题，一个直接且简化的解决方案可能涉及对问题的重新思考，尤其是如何在每一步中有效地更新相邻元素的值而不仅仅是寻找和删除最小元素。

要解决这个问题，我们需要一种能快速找到最小值并对其相邻的值进行更新的数据结构。考虑到题目的数据范围和需求，使用线段树是一个合适的选择。线段树可以在 O(log N) 的时间内进行区间最小查询、更新和删除操作。

思路

构建线段树：用于支持以下操作：

• 查询全局的最小值及其位置。

• 更新单个元素的值。

• “删除”操作不是真正的删除，而是将该位置的值设为一个非常大的值，以使得它在未来的最小值查询中不会被选中。

处理边界情况：当最小值在数组的开头或结尾时，只有一个相邻元素，因此只需要更新一个元素。

执行 K 次操作：

• 使用线段树寻找并获取最小元素和其索引。

• 更新相邻元素的值。

• 将最小元素的值设为极大，视为“删除”。

• 重复上述过程 K 次。

收集和输出结果：在完成所有 K 次操作后，收集剩余的 N-K 个元素并输出。

线段树的设计

线段树中每个节点需要存储：

• 区间的最小值。

• 最小值对应的索引（在多个相同最小值时，使用最靠前的索引）。