解题思路:
考虑到要动态维护最小值,所以用小根堆和双向链表来维护,而且堆顶元素可能因为被相加而变成不是最小,所以还要判断一下是否大小改变,如果有改变把新的值重新放入堆中,依次操作直到找到最小值。
注意事项:
开long long
参考代码:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 500010;
typedef pair<ll, int> PII;
priority_queue<PII, vector<PII>, greater<PII> > heap;
ll e[N], l[N], r[N];
int k, n;
void delect(int k) {
l[r[k]] = l[k];
r[l[k]] = r[k];
e[r[k]] += e[k];
e[l[k]] += e[k];
}
int main(void) {
scanf("%d%d", &n, &k);
r[0] = 1, l[n + 1] = n;
for (int i = 1; i <= n; i++) {
int x;
scanf("%d", &x);
e[i] = x, l[i] = i - 1, r[i] = i + 1;
heap.push({x, i});
}
while (k--) {
auto t = heap.top();
heap.pop();
if (t.first != e[t.second]) heap.push({e[t.second], t.second}), k++;
else delect(t.second);
}
for (int i = r[0]; i != n + 1; i = r[i]) {
printf("%lld ", e[i]);
}
return 0;
}
0.0分
2 人评分
简单的a+b (C语言代码)浏览:544 |
C语言程序设计教程(第三版)课后习题8.3 (C语言代码)浏览:422 |
母牛的故事 (C语言代码)浏览:435 |
C语言程序设计教程(第三版)课后习题5.7 (C语言代码)浏览:585 |
printf基础练习2 (C语言代码)浏览:646 |
C语言程序设计教程(第三版)课后习题8.8 (C语言代码)浏览:546 |
C语言程序设计教程(第三版)课后习题9.3 (C语言代码)浏览:679 |
1126题解浏览:596 |
C二级辅导-统计字符 (C语言代码)浏览:481 |
分解质因数 (C++代码)浏览:1482 |