背景故事 在遥远的魔法王国里，拓拓和思思是两位年轻的魔法学徒。他们发现了一串神秘的魔法宝石，每颗宝石都蕴含着不同的魔力值A1,A2,…,AN。为了提升自己的魔法能力，他们决定进行一项挑战： 规则 ：每次选择魔力值最小的宝石（如果有多颗魔力值相同，就选最左边的那颗），将它从宝石序列中移除。然后，这颗宝石的魔力会传递给相邻的宝石，使它们的魔力值增加被移除宝石的魔力值。 问题描述 给定一串魔法宝石，初始魔力值为A1,A2,…,AN。拓拓和思思需要执行以下操作K次： 1.选择宝石 ：找到当前序列中魔力值最小的宝石。如果有多颗魔力值相同，选择最左边的那颗。 2.移除宝石并传递魔力 ： 移除选中的宝石。 如果这颗宝石左边有相邻宝石 ，则左边宝石的魔力值增加被移除宝石的魔力值。 如果这颗宝石右边有相邻宝石 ，则右边宝石的魔力值增加被移除宝石的魔力值。 最终，输出K次操作后剩下的宝石序列。 输入格式 第一行包含两个整数N和K。 第二行包含N个整数，A1,A2,A3,…,AN。 输出格式 输出N-K个整数，中间用一个空格隔开，代表K次操作后的宝石序列。 样例 输入数据#1 5 3 1 4 2 8 7 输出数据#1 17 7 解释#1 数列变化如下，中括号里的数是当次操作中被选择的数: [1] 4 2 8 7 5 [2] 8 7 [7] 10 7 17 7 数据范围 对于20%的数据，1≤K＜N≤10000。 对于100%的数据，1≤K＜N≤10^5，0≤Ai≤10^8。 c++

<think>好的，我现在得仔细看看这个问题。题目是说，每次移除当前序列中魔力值最小的最左边的宝石，然后它的左右相邻的宝石会加上这个被移除的宝石的魔力值。然后重复这个过程K次，最后输出剩下的序列。 那怎么模拟这个过程呢？直接模拟的话，每次都要找到最小值的位置，然后处理左右，然后更新数组。但问题在于当N和K很大的时候，比如1e5次操作的话，这样的时间复杂度会很高。每次找最小值是O(n)，K次的话总时间复杂度是O(Kn)，这样对于1e5来说，1e5 * 1e5就是1e10次操作，肯定超时了。所以必须得想更高效的方法。 那怎么优化呢？想到可能需要用优先队列或者堆结构来快速找到最小值。但是，每次移除后，左右元素的数值会变化，这会影响到后面的操作。这时候，如何维护这些元素的当前值呢？因为当某个元素被移除后，周围的元素的值会被更新，而这些被更新的元素可能之后会被选中。所以，直接使用堆的话，如果元素的值被修改了，堆中的旧值可能还存在，导致无法正确找到最小值。这个时候，可能需要一个可以动态更新元素的结构，比如一个索引优先队列，或者某种能够支持高效更新和删除的数据结构。 或者，有没有可能使用双向链表来维护宝石的顺序，并且每个节点保存当前的值，以及左右指针。然后，用一个优先队列或者堆来保存每个节点的当前值，以及位置信息。但问题在于，当某个节点被移除后，会影响左右节点的值，这时候这些左右节点的值需要被更新，而堆里的旧值需要被移除或者标记为无效。但普通的堆结构无法处理这种情况，因为堆里的元素无法被动态修改。 这时候想到，可能可以采用一种延迟处理的策略。比如，维护一个优先队列，里面保存每个元素的当前值以及位置，但当一个元素被移除后，检查堆顶的元素是否有效（即是否已经被处理过，或者其保存的值是否已经被更新）。只有当堆顶的元素的值确实是当前的有效值时，才进行处理。否则，就忽略这个堆顶元素，继续弹出下一个元素。 具体来说，每个元素可能需要记录其当前的魔力值，以及是否已经被移除。当处理一个元素时，首先检查它是否已经被移除或者它的值是否已经被修改过。如果是的话，就跳过，否则进行移除操作，并更新左右邻居的值，然后将左右邻居的新值重新加入堆中，或者标记原有堆中的记录为无效。 这可能需要每个节点有一个指针或者索引，指向其在堆中的位置，以便在更新值时能够快速调整堆的结构。但这样实现起来可能比较复杂，尤其是在C++中，因为标准库的优先队列不支持这样的操作。 或者，可以考虑使用一个优先队列，存储的是可能的候选节点，但每次取出堆顶的时候，需要检查该节点是否已经被处理过，或者它的值是否已经过时。如果是的话，就跳过，继续处理下一个堆顶元素。否则，处理该节点，并更新其左右节点的值，同时将这些左右节点的新值加入堆中。这样，堆中可能有很多旧的记录，但每次处理的时候都会先进行有效性检查。 这种方法的时间复杂度如何？每次操作可能需要多次弹出堆顶元素，直到找到一个有效的。假设每个元素被多次加入到堆中，但每次处理的时候会处理掉一次。如果K次操作的话，总的堆操作次数可能接近O(K log N)。这可能可行。 那具体来说，如何实现呢？ 首先，每个节点需要维护其当前的值，是否被移除，以及左右邻居的指针。可以用双向链表的结构来维护宝石的顺序。同时，用一个优先队列（最小堆）来保存每个节点的当前值和位置。但是，堆中的元素可能包含已经被处理过的节点，或者已经被更新过的节点的旧值。所以，每次从堆顶取出元素时，需要检查该节点是否已经被移除，或者该节点的当前值是否等于堆中保存的值。如果不等，说明这个堆中的记录是过时的，应该跳过。 具体步骤： 1. 初始化双向链表，每个节点保存其值、左右指针、是否被移除的标记。 2. 将所有节点的初始值以及它们的索引（或者指针）放入一个优先队列中。优先队列的比较依据是节点的值，以及当值相同时选择左边的。 3. 进行K次操作： a. 从优先队列中取出堆顶元素（最小值，最左边）。 b. 检查该节点是否已经被移除，或者其当前值是否等于堆中的值。如果是无效的，继续弹出堆顶直到找到有效的节点。 c. 找到该节点的左邻居和右邻居。 d. 将该节点标记为已移除，并从链表中删除。例如，左邻居的右指针指向右邻居，右邻居的左指针指向左邻居。 e. 将该节点的值加到左邻居的值中（如果存在左邻居），同样加到右邻居的值中（如果存在右邻居）。 f. 将左邻居和右邻居的新值加入到优先队列中。因为它们的值已经被更新，旧的堆记录可能还在堆中，但会被后续的检查跳过。 4. 最后遍历链表，输出剩余节点的值。 需要注意的是，每个节点可能有多个记录在堆中，对应不同时间的值。但只有最新的值才会在堆中被正确使用。旧的记录会被检查到无效后跳过。 这样，每次操作的时间复杂度主要取决于堆的操作次数。假设每次处理一个节点需要弹出若干无效的堆元素，但每个节点的无效记录最多被弹出一次，那么总的时间复杂度可能为O((N + K) log N)，这在K和N都是1e5的情况下是可行的。 接下来要考虑如何实现双向链表以及节点的管理。可以使用结构体或者类来表示每个节点。例如： struct Node { int value; Node* left; Node* right; bool removed; }; 但动态分配可能比较麻烦，或者在大量数据时效率不够。或者，可以用数组来模拟链表。比如，使用两个数组prev和next来保存每个节点的前驱和后继，再用一个数组values保存当前的值，以及一个removed数组标记是否被移除。这样，对于索引i来说，prev[i]是其前驱，next[i]是其后继，values[i]是当前的值。 初始化时，prev[i] = i-1，next[i] = i+1。注意边界条件，比如i=0时prev是-1，i=N-1时next是-1。 然后，优先队列中存储的元素需要包括节点的当前值以及它的索引。但是，当节点的值被更新后，堆中的旧值不会被自动更新。因此，每次从堆中取出一个元素时，需要比较该元素的索引对应的当前值是否等于堆中保存的值。如果不等于，或者该节点已经被移除，则跳过。 例如，堆中的元素是pair<int, int>类型，其中第一个元素是value，第二个是索引。但为了处理相同值时选择最左边的，可能需要自定义比较函数。或者，堆中的元素可以保存-value和索引，这样用最大堆就能得到最小值。或者，使用优先队列的比较函数，使得当两个元素的值相等时，索引较小的排在前面。 C++的优先队列默认是最大堆，所以我们可以用pair的结构，其中第一个元素是value，第二个是index，并且自定义比较函数，使得当value较小时排在前面，当value相等时，index较小的排在前面。比如： struct Compare { bool operator()(const pair<int, int>& a, const pair<int, int>& b) { if (a.first != b.first) { return a.first > b.first; // 小顶堆，因为优先队列默认是最大的排在前面，所以这里返回true时，a的优先级低，排在后面。 } else { return a.second > b.second; // 当value相等时，索引大的排在后面，所以堆顶是索引较小的。 } } }; priority_queue<pair<int, int>, vector<pair<int, int>>, Compare> pq; 这样，每次弹出的堆顶元素就是当前最小的value，且相同value时最左边的。 然后，每次弹出元素后，检查该元素的索引对应的当前value是否等于堆中的value，并且是否未被移除。如果都满足，则处理该节点。否则，跳过。 处理步骤： 对于弹出的元素（value， index）： 检查： if (removed[index] || values[index] != value) → 无效，跳过。 否则： 将该节点标记为removed[index] = true. 然后，找到其左邻居和右邻居： left = prev[index]; right = next[index]; 如果左存在，那么values[left] += value. 如果右存在，那么values[right] += value. 然后，将左和右的新值插入堆中。 之后，更新链表结构： 如果左存在，则next[left] = right. 如果 right存在，则 prev[right] = left. 这样，链表的结构被维护。 这样，每次处理一个有效节点时，会将其左右邻居的值增加，并将左右邻居的新值入堆。而之前的旧值可能还在堆中，但在之后处理时会被检查到无效（因为它们的values数组已经被更新）。 这样，整个过程可以高效地进行。 现在，测试样例来看： 输入样例： 5 3 1 4 2 8 7 初始化后的各个节点的索引是0到4，对应的值分别是1,4,2,8,7. 初始链表： prev数组：[-1,0,1,2,3] next数组：[1,2,3,4,-1] 初始堆中有这5个元素： (1,0), (4,1), (2,2), (8,3), (7,4) 第一次操作： 取出堆顶元素（1,0）。检查未被移除，且values[0]等于1。处理： 标记removed[0] = true. 左邻居是prev[0] = -1 → 不存在。右邻居是next[0] =1. 所以，右邻居（索引1）的值增加1 → 4+1=5。于是，values[1]变为5。 将（5,1）加入堆。 然后，更新链表：原0的左右是左不存在，右是1。所以，将next[left]（不存在）指向right，prev[right]（索引1）的prev设为-1。 所以，现在的链表结构是： 索引1的prev是-1，next是2。其他节点的关系： prev数组变为：[-1, -1, 1, 2,3] next数组变为：[1,2,3,4,-1] → 但原0已经被移除，索引1的prev变为-1，所以索引1的prev是-1，索引0被移除。 此时，剩下的节点是1（索引1）、2（索引2）、3（索引3）、4（索引4）吗？或者原链表中的节点是索引0被移除，剩下的四个？ 不管怎样，第一次处理后，序列变为5,2,8,7？或者原序列中的索引0被移除，索引1的值变为5，所以序列是5,2,8,7？ 然后，第二次操作： 堆中现在包含的元素有（4,1）（旧值）、（2,2）、（5,1）（新插入的），8,3，7,4，以及可能其他元素？ 但处理的时候，当取出堆顶元素时，会先取出（2,2）吗？ 因为原堆中还有旧的元素，比如（4,1）已经被更新为5，所以当堆中有（4,1）和（5,1）的时候，此时堆中的元素可能被弹出顺序如何？ 比如，假设此时堆中有（4,1）和（5,1）两个元素。当取出（2,2）时，是正确的，因为此时该节点的当前值是否为2？是的，未被处理过。所以第二次操作选中索引2，值为2。 处理： removed[2] = true. 左邻居是prev[2] =1（索引1），右邻居是next[2]=3（索引3）。 左的值变为5+2=7，右的值变为8+2=10. 然后将这两个新值（7,1）和（10,3）插入堆中。 更新链表：索引2被移除，索引1的next指向3，索引3的prev指向1. 第三次操作，需要处理第三个最小值。此时剩下的节点是索引1（7）、3（10）、4（7）吗？ 此时，堆中可能有很多元素。比如，堆中可能有（5,1）（此时该节点的值已经是7了？）或者（7,1）被插入。可能这时候堆中的元素包括（5,1）、（2,2）、（7,1）、（10,3）、（7,4）等等。当弹出堆顶元素时，会找到当前的最小值。 第三次处理时，堆顶可能是7，但有两个节点：索引4的值是7吗？ 比如，第三次操作时，剩下的节点是索引1（7）、3（10）、4（7）吗？ 此时，堆中的元素可能包括： 索引1的值是7，索引3的值是10，索引4的值是7。或者还有其他元素？ 假设第三次处理的是索引4的值7，或者索引1的值7？ 根据规则，当值相同时，选择最左边的。所以此时堆中的元素如果有两个7，比如索引1和索引4，那么应该选择索引较小的，即索引1。 但可能此时，索引1的当前值是7，而索引4的值是7。堆中有元素（7,1）和（7,4）。堆顶是（7,1）。 所以第三次处理的是索引1。这时候： 标记为已移除。然后左邻居不存在（因为prev[1]是-1），右邻居是3。所以，右邻居的值变为10+7=17。 然后，将新值17插入堆。 此时，剩下的节点是索引3和4吗？ 或者，在第三次操作后，索引1被移除，剩下的节点是索引3和4？ 或者可能还有之前的节点？ 总之，经过三次操作后，剩下的两个节点是索引3和4，值分别为17和7。所以输出17 7，与样例一致。 这说明该算法是正确的。 现在，问题的关键是如何高效地实现这个结构，尤其是处理堆中的旧元素。 在C++中，优先队列不支持直接删除或更新元素，所以只能通过延迟处理的方式。也就是说，每次弹出堆顶元素时，检查其对应的值是否有效。如果无效，则跳过。这可能导致堆中存在大量的旧元素，但每个有效元素只会被处理一次。因此，总的时间复杂度应该还是可以接受的，因为每个元素最多被插入堆中O(1)次？或者每次修改都可能插入一次？ 比如，每个节点在被左右邻居移除时，可能会被多次修改值，导致多次插入堆中。例如，某个节点的初始值是4，然后被更新到5，再被更新到7，每次更新都会有一个新的元素被插入堆中。因此，堆中的元素总数可能会是O(K + N)。假设每次处理一个有效节点，会产生两个新元素插入堆（左右邻居的更新），那么总共有O(K)次有效处理，每次产生两个元素，所以堆的总元素数是O(N + K)。每次堆操作是O(log (N+K))，总时间复杂度是O( (N + K) log (N + K) )。 对于N=1e5，K=1e5的情况，N+K=2e5，log是20左右，所以总操作次数是2e5 * 20 =4e6，这应该可以通过时间限制。 现在，如何实现呢？ 具体的步骤： 1. 读取N和K，然后读取数组A。 2. 初始化prev和next数组，每个元素的prev是i-1，next是i+1。边界条件是prev[0]=-1，next[N-1] =-1。 3. 初始化values数组为输入的数组。 4. 初始化一个removed数组，所有元素初始化为false。 5. 将每个元素的（value, index）插入优先队列。 6. 进行K次有效操作： a. 循环：从优先队列中取出堆顶元素（value, index）。 b. 检查该元素是否已经被移除（removed[index]为true），或者当前values[index] != value。如果是，跳过这个元素，继续循环。 c. 否则，处理这个元素： i. removed[index] = true. ii. 找到左邻居left_idx = prev[index], 右邻居right_idx = next[index]. iii. 如果left_idx != -1： values[left_idx] += value. 将（values[left_idx], left_idx）插入堆中. iv. 同理，如果right_idx != -1： values[right_idx] += value. 将（values[right_idx], right_idx）插入堆中. v. 更新链表结构：将left_idx的next指向right_idx，将right_idx的prev指向left_idx. vi. 计数器减一，直到完成K次处理。 7. 处理完成后，遍历链表，收集剩下的元素。如何遍历链表呢？可以找到链表的头部，即找到第一个未被移除的元素，然后根据next指针遍历。或者，可以使用一个数组，逐个检查每个元素是否未被移除，然后按照链表顺序收集。 但是，链表的结构可能已经被修改，所以直接遍历每个未被移除的元素的顺序可能不正确。例如，假设原链表是0->1->2->3->4，其中0被移除，链表变成1->2->3->4。然后1的prev是-1，next是2。所以正确的顺序是1,2,3,4。所以，正确的遍历方法是找到头节点（即prev为-1的节点），然后根据next指针遍历。 所以，如何找到头节点？ 可以初始化头节点为0，然后循环判断该节点是否被移除。如果被移除，则头节点变成next[head]。直到找到一个未被移除的节点。或者，这可能有问题。或者，可以维护头节点和尾节点，但可能比较复杂。 更简单的方法是，遍历所有节点，找到未被移除的节点，然后根据链表结构来遍历。例如，找到第一个未被移除的节点，然后根据next指针遍历，直到结束。 或者，在每次处理后，链表的结构已经被正确维护，所以可以通过prev和next数组来遍历剩下的节点。例如，头节点是某个未被移除的节点，其prev是-1。所以，可以找到所有未被移除的节点中，prev为-1的节点作为头节点，然后顺序遍历。 例如： int current = 0; while (current != -1) { if (!removed[current]) { // 这是头节点吗？可能不是，因为可能之前的节点被移除了。例如，原头节点是0，被移除后，头节点是1，其prev是-1？ // 所以，正确的头节点是第一个未被移除的节点，其prev为-1. break; } current = next[current]; } 但这个方法可能无法正确找到头节点。例如，假设原链表的头节点是0，被移除后，头节点变成1，其prev被设置为-1。所以，在prev数组中，1的prev是-1。所以，正确的头节点是1。所以，正确的遍历方法是找到所有未被移除的节点中，prev为-1的那个节点作为头节点。 所以，可以遍历所有节点，找到未被移除的，且prev为-1的节点。这需要O(N)时间，但N可能很大，1e5，这会不会有问题？ 或者，在每次移除节点时维护头节点和尾节点。例如，当移除头节点时，新的头节点是其next节点。这样，可以维护一个变量来记录当前链表的头节点，这样在最后遍历时不需要遍历所有节点。但这样会增加维护的复杂度。 或者，在最后遍历时，从prev数组中找到所有未被移除的节点，并记录它们的顺序。或者，可以采用以下方式： 遍历整个数组，收集未被移除的节点，然后根据prev和next数组的顺序重新构建顺序。 这似乎比较复杂。或者，可以采用以下方法： 使用一个数组result，然后找到链表的头节点（即prev为-1的未被移除的节点）。然后，依次访问next指针，直到到达尾节点。将每个未被移除的节点的值加入结果数组。 例如： int current = -1; // 找头节点：prev为-1的未被移除的节点 for (int i = 0; i < N; ++i) { if (!removed[i] && prev[i] == -1) { current = i; break; } } vector<int> res; while (current != -1) { res.push_back(values[current]); current = next[current]; } 输出res中的元素。 这应该可以得到正确的顺序。 综上，整个算法的步骤是可行的。现在需要考虑数据结构的选择。例如，prev和next数组可以用数组实现，每个元素是int类型，初始化为i-1和i+1。values数组保存当前每个节点的值。removed数组保存是否被移除。 现在，针对数据范围，N和K是1e5，需要处理大量的堆操作。所以在C++中，需要尽可能高效的实现。使用priority_queue，但要注意每次插入元素的时间复杂度。 现在，编写代码的大致步骤： 1. 读取输入N和K，以及数组A。 2. 初始化prev、next、values、removed数组。 3. 创建优先队列，并将所有节点的初始值入队。 4. 进行K次有效操作： while (K > 0) { auto top = pq.top(); pq.pop(); int val = top.first; int idx = top.second; if (removed[idx] || values[idx] != val) continue; // 处理这个节点 removed[idx] = true; K--; int left = prev[idx]; int right = next[idx]; // 更新左右邻居的值，并插入堆中 if (left != -1) { values[left] += val; pq.push({values[left], left}); next[left] = right; } if (right != -1) { values[right] += val; pq.push({values[right], right}); prev[right] = left; } } 5. 收集结果： 找到头节点，然后遍历链表。 但这里有一个问题，当处理一个节点时，如何更新prev和next数组？ 例如，当移除idx时，其左邻居的next应该指向idx的右邻居，右邻居的prev应该指向左邻居。所以，在处理idx时，修改其左邻居的next和右邻居的prev。 例如： left = prev[idx]; right = next[idx]; 如果left != -1 → next[left] = right; 如果 right != -1 → prev[right] = left; 所以，在代码中，在更新左右邻居的prev和next时，应该这样做： if (left != -1) { next[left] = right; } if (right != -1) { prev[right] = left; } 但这段代码应该放在哪里？例如，当处理完该节点后，需要将左右邻居的指针连接起来。这应该在处理该节点时完成，无论是否更新左右的值。 哦，对。无论该节点的左右邻居是否被更新，他们的prev和next指针必须被正确修改，以维护链表的结构。所以，在代码中，当处理idx时： 处理步骤： removed[idx] = true; int left = prev[idx]; int right = next[idx]; // 更新左的next指向right if (left != -1) { next[left] = right; } // 更新右的prev指向left if (right != -1) { prev[right] = left; } // 然后，如果左存在，则其值增加val if (left != -1) { values[left] += val; pq.push({values[left], left}); } if (right != -1) { values[right] += val; pq.push({values[right], right}); } 这样，链表的结构被正确维护。例如，当移除idx后，左和右的指针被正确连接。 这样，在收集结果时，可以通过链表结构来遍历未被移除的节点。 现在，测试样例中的第一次操作： 移除索引0，左是-1，右是1。所以，左不存在。所以，next[left]（不存在）无需处理。处理右的prev：将prev[1]设为-1？ 是的。所以，prev[1] = left（left是-1）。所以，此时索引1的prev是-1，next是2。索引0被移除。 这样，链表结构正确。 第二次操作，处理索引2。其左是1，右是3。处理后的链表结构是，左的next（索引1的next）设为3。右的prev（索引3的prev）设为1。所以，索引2被移除，链表结构变成1->3->4。索引3的prev是1，索引4的prev是3，索引1的next是3。 第三次操作处理索引4吗？或者处理索引1？或者处理索引3？ 第三次操作处理的是哪个节点？ 第三次处理时，假设堆中有索引1的值为5+2=7（在第一次处理时，右邻居索引1的值被加1→4→5，然后在第二次处理索引2时，左邻居索引1的值被加2→5+2=7？或者可能我之前的例子中的数值变化是否正确？ 例如，第一次操作： 索引0被移除，值是1。右邻居是1，所以索引1的值变为4+1=5。此时，堆中插入（5,1）。 第二次操作，处理索引2，初始值为2。左右邻居是1和3。索引1的值加2变为5+2=7，索引3的值加2变为8+2=10。所以，插入（7,1）和（10,3）。 此时，堆中有这两个元素。第三次操作时，堆顶的元素可能是什么？ 假设第三次操作时，堆中的元素包括（7,1）、（10,3）、（7,4）？因为初始的索引4的值是7，未被处理过。此时，堆顶的元素是（7,1）吗？ 是的，因为当堆中的元素是（7,1）和（7,4）时，比较它们的索引，1 <4，所以堆顶是（7,1）。 所以第三次处理索引1，其当前值是否为7？是的。此时，索引1被移除。其左邻居是prev[1] =-1，右邻居是3。所以，处理后的链表结构是： next[-1]不存在，但处理索引1的右邻居是3，所以： next[left] → left是-1，无需处理。 prev[right] → right是3，其prev被设置为-1。索引3的prev变成-1. 然后，索引1的左右邻居的值更新： 左不存在，所以右邻居3的值变为10 +7=17. 所以，堆中插入（17,3）和（如果右邻居存在的话，比如索引3的右是4，那么索引4的值是7+7=14？不，此时索引1的右邻居是3，所以只有右邻居的索引3的值被加7。索引3的值是10+7=17。此时，将（17,3）插入堆。 此时，剩下的节点是索引3和4吗？ 是的。索引3的prev是-1（因为其左邻居是1，被移除后，prev[right]被设置为left，即-1。所以索引3的prev是-1。它的next是4。索引4的prev是3。所以链表是3→4。所以，遍历链表时，得到17和7的值，符合样例输出。 所以，该算法是正确的。 现在，编写代码需要注意以下几点： 1. 优先队列的比较函数必须正确，当值相同时，选择索引较小的。 2. 在每次处理节点时，正确更新链表结构，即prev和next数组。 3. 在收集结果时，正确遍历链表结构。 现在，编写代码的大致结构： #include <iostream> #include <vector> #include <queue> using namespace std; struct Compare { bool operator()(const pair<int, int>& a, const pair<int, int>& b) { if (a.first != b.first) { return a.first > b.first; // 小顶堆，a的value大于b时，a的优先级低。所以堆顶是最小的value。 } else { return a.second > b.second; // value相等时，索引大的排在后面，所以堆顶是索引较小的。 } } }; int main() { int N, K; cin >> N >> K; vector<int> A(N); for (int i = 0; i < N; ++i) { cin >> A[i]; } vector<int> prev(N); vector<int> next(N); vector<int> values = A; vector<bool> removed(N, false); for (int i = 0; i < N; ++i) { prev[i] = i - 1; next[i] = i + 1; } prev[0] = -1; next[N-1] = -1; priority_queue<pair<int, int>, vector<pair<int, int>>, Compare> pq; for (int i = 0; i < N; ++i) { pq.push({values[i], i}); } while (K > 0) { auto top = pq.top(); pq.pop(); int val = top.first; int idx = top.second; if (removed[idx] || values[idx] != val) { continue; } // 处理该节点 removed[idx] = true; K--; int left = prev[idx]; int right = next[idx]; // 更新左右邻居的指针 if (left != -1) { next[left] = right; } if (right != -1) { prev[right] = left; } // 更新左右邻居的值 if (left != -1) { values[left] += val; pq.push({values[left], left}); } if (right != -1) { values[right] += val; pq.push({values[right], right}); } } // 收集结果 vector<int> res; // 找到头节点：未被移除的，且prev为-1的节点 int current = -1; for (int i = 0; i < N; ++i) { if (!removed[i] && prev[i] == -1) { current = i; break; } } while (current != -1) { res.push_back(values[current]); current = next[current]; } for (int i = 0; i < res.size(); ++i) { if (i > 0) cout << " "; cout << res[i]; } cout << endl; return 0; } 这样，应该可以正确处理样例。 现在，测试样例输入： 5 3 1 4 2 8 7 初始prev数组是[-1,0,1,2,3], next数组是[1,2,3,4,-1]. 初始堆中的元素是（1,0）、（4,1）、（2,2）、（8,3）、（7,4）。 第一次弹出（1,0）：未被移除，values[0]是1。处理： removed[0] = true. left=prev[0]=-1，right=next[0]=1. 更新指针：next[left]（不存在）和prev[right] → prev[1] = -1. 所以，此时prev[1] =-1，next[1]=2. 然后，left不存在，所以只处理right=1。values[1] +=1 →4+1=5。将（5,1）入堆。 第二次循环，弹出堆中的下一个元素。此时堆顶可能是（2,2），因为其他元素可能还在堆中。假设弹出（2,2），未被移除，values[2]等于2。处理： removed[2] = true. left=1，right=3. 更新指针：next[1]=3，prev[3]=1. 然后，处理left和 right： values[1] +=2 →5+2=7。插入（7,1）. values[3] +=2 →8+2=10。插入（10,3）. 第三次循环，弹出堆顶元素。此时堆中有（4,1）（旧值），（5,1）（旧值），（7,1）（新值），（10,3），（7,4）等。当弹出（7,1）时，检查是否有效。此时，values[1]是7，未被移除。处理： removed[1]=true. left=prev[1]=-1，right=next[1]=3. 更新指针：next[left]不存在，prev[right]=-1. 此时，right=3的prev被设为-1. 处理右邻居3的值：values[3] +=7 →10+7=17。插入（17,3）. 此时，K=0，循环结束。 收集结果时，找到未被移除且prev为-1的节点。此时，索引3的prev是-1（因为其prev被设置为-1吗？在处理第三次操作时，当处理索引1时，其right是3。此时，prev[3]被设置为left=prev[1]=-1。所以是的。索引3的prev是-1。未被移除，所以current=3。然后next[3]是4。索引4未被移除。所以，收集17（values[3]=17）和7（values[4]=7）。输出17 7，正确。 这样，该代码是正确的。</think>要解决这个问题，我们需要高效地模拟每次移除魔力值最小的宝石并更新相邻宝石的过程。直接模拟会导致超时，因此需要使用优先队列（最小堆）来快速找到最小值，并结合双向链表维护宝石的当前顺序。 ### 方法思路 1. **优先队列**：用于快速找到当前魔力值最小的宝石。队列中存储的是宝石的值和索引。 2. **双向链表**：维护宝石的顺序，以便在移除某个宝石后快速更新相邻宝石的指针。 3. **延迟处理**：每次从优先队列取出元素时，检查其有效性（是否已被移除或值已过时），若无效则跳过，直到找到有效的宝石进行处理。 ### 解决代码 ```cpp #include <iostream> #include <vector> #include <queue> using namespace std; struct Compare { bool operator()(const pair<int, int>& a, const pair<int, int>& b) { if (a.first != b.first) { return a.first > b.first; // 小顶堆，值小的优先 } else { return a.second > b.second; // 值相同时，索引小的优先 } } }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N, K; cin >> N >> K; vector<int> A(N); for (int i = 0; i < N; ++i) { cin >> A[i]; } vector<int> prev(N), next(N); vector<int> values(A.begin(), A.end()); vector<bool> removed(N, false); for (int i = 0; i < N; ++i) { prev[i] = i - 1; next[i] = i + 1; } prev[0] = -1; next[N - 1] = -1; priority_queue<pair<int, int>, vector<pair<int, int>>, Compare> pq; for (int i = 0; i < N; ++i) { pq.emplace(values[i], i); } while (K > 0) { auto [val, idx] = pq.top(); pq.pop(); if (removed[idx] || values[idx] != val) continue; removed[idx] = true; K--; int left = prev[idx]; int right = next[idx]; // 更新左右邻居的指针 if (left != -1) next[left] = right; if (right != -1) prev[right] = left; // 更新左右邻居的值并加入堆 if (left != -1) { values[left] += val; pq.emplace(values[left], left); } if (right != -1) { values[right] += val; pq.emplace(values[right], right); } } // 收集结果 vector<int> res; int current = -1; for (int i = 0; i < N; ++i) { if (!removed[i] && prev[i] == -1) { current = i; break; } } while (current != -1) { res.push_back(values[current]); current = next[current]; } for (size_t i = 0; i < res.size(); ++i) { if (i > 0) cout << ' '; cout << res[i]; } cout << '\n'; return 0; } ``` ### 代码解释 1. **输入处理**：读取初始宝石数量和操作次数，以及各宝石的初始魔力值。 2. **双向链表初始化**：维护每个宝石的前驱和后继指针。 3. **优先队列初始化**：将所有宝石的初始值和索引加入队列，确保每次取出最小值。 4. **处理操作**：每次从队列中取出最小值，检查有效性后更新相邻宝石的魔力值和链表指针，并将更新后的值重新加入队列。 5. **结果收集**：遍历链表，输出剩余宝石的魔力值。 该方法通过优先队列和双向链表的结合，高效处理了每次操作，确保在较大数据规模下仍能高效运行。