优先队列 + map

解题思路:
数据为10e5  暴力n^2 肯定会超时

可以利用小根堆来做

注意事项:
由于value不断的加可能超过INT_MAX,所以value类型为long long
参考代码:

#include<iostream>
#include<vector>
using namespace std;
#include<queue>
#include<map>
typedef pair<long long, long long> pa_ir;
int main() {
	int n, k;
	cin >> n >> k;
	vector<long long> arr(n + 2, 0);
	map<int, pa_ir> idex;//map的key为元素的下标，而pa_ir来记录该以key为下标的前一个位置和后一个位置的下标
	idex[0] = pa_ir(-1, 1);//来保障最小值为第一个值时可以向中间值一样操作
	priority_queue<pa_ir, vector<pa_ir>, greater<pa_ir>> pri;//小根堆
	for (int i = 1; i <= n; i++) {//将元素进数组和小根堆
		long long x;
		cin >> x;
		arr[i] = x;
		idex[i] = pa_ir(i - 1, i + 1);
		pri.push(pa_ir(x, i));
	}
	idex[n + 1] =  pa_ir(n, -1);//来保障最小值为最后一个值可以向中间值一样操作，即总体的map值比arr数组大2

	while (k--) {
		auto t = pri.top();
		pri.pop();
		//t.first != arr[t.second]来判断最小值是否更改，前一个出的会影响小根堆的值
		if (t.first != arr[t.second]) {//当小根堆出去一个元素时，会影响周围的值，假设小根堆的第二个值是第一个小根堆的相邻值
		//当第一个值出小根堆时会影响第二个的值，此时第二小的值会被该变，可能不会是最小值，此时再重新入小根堆，可保证最小值在堆顶
			pri.push({ arr[t.second], t.second });
			k++;

		}
		else {
			int x = t.second;//删除元素的下标 
			arr[idex[x].first] += arr[x];//idex[x].first为下标为x的前一个元素
			arr[idex[x].second] += arr[x];//idex[x].second为下标为x的后一个元素
			
			//此时以x为元素的下标需要在map中删除，在此之前要更新map中元素的前后关系
			idex[idex[x].first].second = idex[x].second;
			idex[idex[x].second].first = idex[x].first;
			
			//删除x
			auto it = idex.find(x);
			idex.erase(it);
		}
	}
	此时map中it.second.second为最终留下的元素
	for (auto it : idex) {
		if (it.second.second == n + 1) break;
		cout << arr[it.second.second] << " ";
	}
	return 0;
}