开02优化并且禁止流同步能过此题
很容易想到使用双向链表来储存这个数据
重要的是维护小顶堆的时候需要判断之前已经变化了的值,不能作为合法值去执行删除操作,可以在此时更新小顶堆
#pragma GCC optimize(2)
#include <iostream>
#include <queue>
#include <vector>
#include <utility>
using ll = long long;
const int N = 5e5 + 7;
ll nums[N];
int left[N], right[N];
using pii = std::pair<ll ,int>;
std::priority_queue<pii,std::vector<pii>,std::greater<pii>> q;
int n,k;
void deleteIndex(int index)
{
right[left[index]] = right[index];
left[right[index]] = left[index];
nums[left[index]] += nums[index];
nums[right[index]] += nums[index];
}
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
std::cin>>n>>k;
right[0] = 1, left[n+1] = n;
for(int i = 1;i<=n;i++)
{
std::cin>>nums[i];
left[i] = i-1;
right[i] = i+1;
q.push({nums[i],i});
}
for(int i = 0;i<k;i++)
{
auto t = q.top();
q.pop();
ll num = t.first;
int index = t.second;
//如果此时发现下标对应的真实值与队列中不一致时,则说明该下标对应的值发生了改变,将改变后的值重新放入队列中,并回退一次无效操作
if(num!=nums[index]) q.push({nums[index],index}),k++;
else deleteIndex(index);
}
for(int i = right[0];i != n + 1;i = right[i])
std::cout<<nums[i]<<" ";
return 0;
}