题目描述
给定一个长度为 N 的整数数列:A1, A2, . . . , AN。你要重复以下操作 K 次:
每次选择数列中最小的整数(如果最小值不止一个,选择最靠前的),将其删除。并把与它相邻的整数加上被删除的数值。输出 K 次操作后的序列
第一行包含两个整数 N 和 K。
第二行包含 N 个整数,A1, A2, A3, . . . , AN。
输出 N − K 个整数,中间用一个空格隔开,代表 K 次操作后的序列。
样例
样例输入
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 × 105,0 ≤ Ai ≤ 108
算法1
小根堆+数组模拟链表
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N = 500010;
int n,k;
typedef long long LL;
typedef pair<LL ,LL> PII;
LL v[N], l[N], r[N];
//双向链表的删除操作, 删除x结点
void del(int x)
{
l[r[x]] = l[x] , r[l[x]] = r[x];
v[l[x]] += v[x], v[r[x]] += v[x];
}
int main()
{
scanf("%d%d",&n,&k);
priority_queue<PII ,vector<PII>,greater<PII>> heap;
r[0] = 1, l[n+1] = n;
for(int i=1;i<=n;i++)
{
scanf("%lld",&v[i]);
l[i]=i-1,r[i]=i+1;
heap.push({v[i],i});
}
while(k--)
{
auto t = heap.top(); heap.pop();
//如果v发生变化, 则目前的元素不一定是最小值, 需要重新放入堆中
if (t.first != v[t.second]) heap.push({v[t.second], t.second}), k ++;
else del(t.second);
}
int hh = r[0];
while(hh!=n+1)
{
cout<<v[hh]<<" ";
hh = r[hh];
}
return 0;
}