问题描述

给定一个长度为 NN 的整数数列：A1,A2,…,ANA1​,A2​,…,AN​。你要重复以下操作 KK 次：

每次选择数列中最小的整数（如果最小值不止一个，选择最靠前的），将其删除。并把与它相邻的整数加上被删除的数值。

输出 KK 次操作后的序列。

输入格式

第一行包含两个整数 NN 和 KK。

第二行包含 NN 个整数，A1,A2,A3,…,ANA1​,A2​,A3​,…,AN​。

输出格式

输出 N−KN−K 个整数，中间用一个空格隔开，代表 KK 次操作后的序列。

样例输入

5 3
1 4 2 8 7

样例输出

17 7

样例说明

数列变化如下，中括号里的数是当次操作中被选择的数：

[1] 4 2 8 7

5 [2] 8 7

[7] 10 7

17 7

评测用例规模与约定

对于 20% 的数据，1≤K<N≤10000。

对于 100%的数据，1≤K<N≤5×10^5，0≤Ai≤10^8。

运行限制

语言	最大运行时间	最大运行内存
C++/C	1s	256M

解法一：双链表

最直接的想法是将数列存在一个双链表中，每次查找双链表中data值最小的节点，使用prior、next找到左右节点，并更新相应数值之后，将节点从链表中删除。但是查找函数findMinNode最坏的情况是从表头一直查到表尾O(N)，重复K次后时间复杂度为O(N*K)，题目限制最大运行时间为1s，非常容易超时。

#include <bits/stdc++.h>
using namespace std;

typedef struct node{
	int data;
	struct node *prior;
	struct node *next;
}LinkNode; 

class dlinklist{
	private:
		LinkNode *head;
		
	public:
		LinkNode *end;
		//构造函数
		dlinklist():head(NULL), end(NULL){}
		
		//添加节点到链尾
		void append(int value, int index){
			LinkNode* N = (LinkNode*)malloc(sizeof(LinkNode));    //创建该节点 
			N->data = value;
			N->prior = NULL;
			N->next = NULL;
			
			//如果初始链表为空
			if(!head){
				head = end = N;
			}else{                  //否则 
				end->next = N;
				N->prior = end;
				end = N;
			}
		}
		
		//删除指定节点, 需要输入节点的指针，因此需要一个vector存储指向每个节点的指针 
		void deleteNode(LinkNode* node){
			if(node->prior){
				node->prior->next = node->next;
			}else{
				head = node->next;
			}
			if(node->next){
				node->next->prior = node->prior;
			}else{
				end = node->prior;
			}
			delete node;    //释放内存 
		} 
		
		//查找链表中最小的节点
		LinkNode* findMinNode(){
			LinkNode* min = head;
			LinkNode* current = head;
			while(current){
				if(current->data < min->data){
					min = current;
				}
				current = current->next;
			}
			return min;
		}
		
		//输出链表中的所有值
		void output(){
			LinkNode* current = head;
			while(current){
				cout << current->data << " ";
				current = current->next; 
			}
		}
		
		//判断链表是否为空
		bool isEmpty(){
			return  head == NULL;
		} 
};

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int N, K;
	cin >> N >> K;
	
	//创建双链表
	dlinklist list;
	
	vector<LinkNode*> nodes(N); 
	
	for(int i = 0; i < N; i++){
		int num;
		cin >> num;
		list.append(num, i);
		nodes[i] = list.end;
	} 
	
	//K次操作
	for(int j = 0; j < K; j++){
		
		if(list.isEmpty()){
			break;
		}
		
		LinkNode* min = list.findMinNode();
		
		int minvalue = min->data;
		
		//更新相邻节点的值 
		if(min->prior){
			min->prior->data += minvalue;
		}
		if(min->next){
			min->next->data += minvalue;
		}
		
		list.deleteNode(min); //删除该节点 
	}
	
	list.output();
	
	return 0; 
}

测试结果：

解法二：优先队列

用双链表实现元素的删除操作非常方便，但是找到最小值并且更新临近元素仍需要多次遍历整个链表导致时间复杂度达到O(N*K)，题目要求时间限制为1s，当N和K足够大时算法一定会超时。但是K次遍历是题目要求的，那么降低时间复杂度显然就要从N入手。优先队列可以很好的解决这个问题。

优先队列简而言之就是给所有元素一个优先级（一般为元素数值），越小越优先或者越大越优先（最大优先队列/最小优先队列）。队头始终是最值，队头弹出后，新的队头仍保支持为队列中的最值。一般使用二叉堆实现，时间复杂度为，竞赛中不需要自己实现，可以使用STL priority_queue。

这时，能从链表中快速的找到最小值，但是应该如何在链表中对应最小值的位置呢，如果还是用上面的链表定义方法显然需要从表头开始遍历，如果这么做优先队列就没有使用的必要了。此时用极简链表可以很好的解决这个问题：

大致思路：用优先队列找最小值t，时间复杂度为，在链表上找到t的位置，时间复杂度为O(1)，用链表处理删除和临近更新，时间复杂度为O(1)，一次计算的时间复杂度总共为，重复执行K次为。

#include <bits/stdc++.h>
using namespace std;

const int N = 5e5 + 10;
long long v[N];
int L[N], R[N];

void del(int x){
    R[L[x]] = R[x];   // 删除第x个节点 
    L[R[x]] = L[x];
    v[L[x]] += v[x];  // 更新左右邻居 
    v[R[x]] += v[x];
}

int main(){
    int n, k;
    cin >> n >> k;
    
    priority_queue<pair<long long, int>, vector<pair<long long, int> >, greater<pair<long long, int> > > Q;
    
    R[0] = 1;
    L[n + 1] = n;
    
    // 输入数据
    for (int i = 1; i <= n; i++) {
        cin >> v[i];
        L[i] = i - 1;
        R[i] = i + 1;
        
        Q.push(make_pair(v[i], i));
    }

    while (k--) {
        auto p = Q.top();
        Q.pop();

        // 如果当前节点的值已被更新，跳过并重新加入队列
        if (p.first != v[p.second]) {
            Q.push(make_pair(v[p.second], p.second));
            k++;  // 重新进行一轮操作
        } else {
            del(p.second);
        }
    }

    // 输出结果
    int t = R[0];
    while (t != n + 1) {
        cout << v[t] << " ";
        t = R[t]; 
    }
    return 0;
}

测试结果：