AcWing 4961. 整数删除
原题链接
中等
作者:
tyEyyu53
,
2024-04-08 22:52:42
,
所有人可见
,
阅读 4
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e6 + 10;
int n, k;
int l[N], r[N], e[N], del[N];
int con[N];
int val, id;
typedef pair<int, int> PII;
priority_queue<PII, vector<PII>, greater<PII>> heap;
void dele(int i)
{
r[l[i]] = r[i];
l[r[i]] = l[i];
del[id] = 1;
}
signed main()
{
cin >> n >> k;
for (int i = 1; i <= n; i++)
{
cin >> e[i];
heap.push({e[i], i});
l[i] = i - 1;
r[i] = i + 1;
}
while (k)
{
auto t = heap.top();
heap.pop();
val = t.first;
id = t.second;
if (del[id])
continue;
if (!con[id])
{
if (l[id] >= 1)
con[l[id]] += val;
if (r[id] <= n)
con[r[id]] += val;
dele(id);
k--;
}
else
{
e[id] += con[id];
heap.push({val + con[id], id});
con[id] = 0;
}
}
for (int i = 1; i <= n; i++)
{
if (!del[i])
cout << e[i] + con[i] << " ";
}
return 0;
}