题目描述
给定一个长度为 $N$ 的整数数列:$A_1, A_2, . . . , A_N$。
你要重复以下操作 $K$ 次:
每次选择数列中最小的整数(如果最小值不止一个,选择最靠前的),将其删除,并把与它相邻的整数加上被删除的数值。
输出 $K$ 次操作后的序列。
输入格式
第一行包含两个整数 $N$ 和 $K$。
第二行包含 $N$ 个整数,$A_1, A_2, A_3, . . . , A_N$。
输出格式
输出 $N − K$ 个整数,中间用一个空格隔开,代表 $K$ 次操作后的序列。
数据范围
对于 $20\\%$ 的数据,$1 ≤ K < N ≤ 10000$。
对于 $100\\%$ 的数据,$1 ≤ K < N ≤ 5 × 10^5$,$0 ≤ A_i ≤ 10^8$。
输入样例:
5 3
1 4 2 8 7
输出样例:
17 7
C++ 代码
#include <iostream>
#include <algorithm>
#define int long long
using namespace std;
const int N = 500010;
typedef pair<int, int> PII;
PII heap[N];
int heap_size; //小根堆的大小
int a[N], l[N], r[N]; // l[i] 存储下标为 i 的值的前一个值的下标, r[i] 同理
int delta[N]; // 真值为原本的值 + delta
int n, k;
void down(int u)
{
int t = u;
// 当左孩子存在,并且左孩子的值要小于根节点,或者左孩子的值等于根节点的值,但左孩子下标更小时,需要交换
if((u << 1) <= heap_size && (heap[u << 1].first < heap[t].first || (heap[u << 1].first == heap[t].first && heap[u << 1].second < heap[t].second))) t = u << 1;
// 当右孩子存在,并且右孩子的值要小于根节点,或者右孩子的值等于根节点的值,但右孩子下标更小时,需要交换
if((u << 1 | 1) <= heap_size && (heap[u << 1 | 1].first < heap[t].first || (heap[u << 1 | 1].first == heap[t].first && heap[u << 1 | 1].second < heap[t].second))) t = u << 1 | 1;
if(t != u)
{
swap(heap[t], heap[u]);
down(t);
}
return ;
}
void debug()
{
for(int i = 1;i <= heap_size;i ++)
{
cout << heap[i].first + delta[heap[i].second] << " " << heap[i].second << endl;
}
cout << endl << "----------------------------- " << endl;
return ;
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> k;
r[0] = 1, l[n + 1] = n;
heap_size = n;
for(int i = 1;i <= n;i ++)
{
cin >> a[i];
heap[i] = {a[i], i};
l[i] = i - 1, r[i] = i + 1;
}
for(int i = n >> 1;i >= 1;i --) down(i);
while(k --)
{
while(delta[heap[1].second] > 0)
{
heap[1].first += delta[heap[1].second];
a[heap[1].second] += delta[heap[1].second]; //下面要清空 delta, 故须先修正 a
delta[heap[1].second] = 0; //置为0是为了避免重复计算
down(1);
}
// 在两边加上删除值的大小
delta[l[heap[1].second]] += heap[1].first;
delta[r[heap[1].second]] += heap[1].first;
// 在链表中删除该节点
r[l[heap[1].second]] = r[heap[1].second];
l[r[heap[1].second]] = l[heap[1].second];
swap(heap[1], heap[heap_size]);
heap_size --;
down(1);
//debug();
}
// 最后,按序输出链表
int cur = 0;
while(r[cur] != n + 1)
{
cout << a[r[cur]] + delta[r[cur]] << " ";
cur = r[cur];
}
return 0;
}