-
题意:
动态维护一堆数据的最小值, 且要保证数据有序,且能快速删除和修改数据 -
思路:
考虑优先队列(堆)+ 双链表
细节:
1. 会爆int, printf 输出的时候记得用 lld 😭
2. 堆heap中的元素由于不能直接修改,所以只能先把每个元素的增量记录下来,在pair从堆顶弹出的时候判断增量如果不为0就重新把正确的pair push进去
3. 每个元素的输入编号就可以作为链表节点的编号, 这样就可以实现O(1)查询链表元素
4. heap里面存pair就可以保证相同的最小值一定取的是序号最小的
AC代码:
#include <iostream>
#include <queue>
using namespace std;
typedef long long LL;
typedef pair<LL, int> PII; // 一定要是 long long
const int NN = 5e5 + 10;
int h = -1, l[NN], r[NN], idx = 2; // 0 1 分别是左右端点, 所以从2开始
int N, K;
LL add[NN], e[NN];
priority_queue<PII, vector<PII>, greater<PII>> heap; // 小根堆
void change(int t){
e[l[t]] += e[t], e[r[t]] += e[t];
add[l[t]] += e[t], add[r[t]] += e[t];
r[l[t]] = r[t], l[r[t]] = l[t];
}
int main()
{
cin >> N >> K;
r[0] = 1, l[1] = 0;
for (int i = 2, a; i < N + 2; i ++){ // 坑点: 这里用的是头插法, 所以第一个数会被插到最后一个
scanf("%d", &a);
// e[idx] = a, ne[idx] = h, h = idx ++;
e[idx] = a, l[idx] = 0, r[idx] = r[0], l[r[0]] = idx, r[0] = idx ++;
heap.push({a, i});
}
while (K --){
auto t = heap.top();
heap.pop();
while (add[t.second]){ // 必须用while, 因为必须要删除K次
t.first += add[t.second];
add[t.second] = 0;
heap.push(t);
t = heap.top();
heap.pop();
}
change(t.second);
}
int cur = l[1]; // 从后往前遍历
while (cur){
printf("%lld ", e[cur]); // lld !!!!
cur = l[cur];
}
return 0;
}