瞬间定位一个数的左边或者右边,需要用到双向链表。
在过程中不断维护最小值,需要用到堆。
所以定义一个pair类型优先队列,每次取出堆顶进行删除,并且同时让删除元素的左右元素加上其值。
同时需要注意,在删除元素之后,我们又对两个元素进行了值的增加,所以这时候堆里对应的值和元素真实对应的值是不同的,则这时候取出来的最小值对应的下标不一定就是最小值了,如果我们扫到了真实值和堆中值不同的元素,就要重新把改变后的元素压入堆,这样才能保证完全正确。
代码:
#include<iostream>
#include<queue>
using namespace std;
const int N = 5e5 + 10;
#define pii pair<long long,int>int n, k;
long long v[N], l[N], r[N];int main() {cin >> n >> k;r[0] = 1, l[n + 1] = n;priority_queue< pii, vector<pii>, greater<pii> >heap;//first存value值,second存下标for (int i = 1; i <= n; i++) {cin >> v[i];l[i] = i - 1, r[i] = i + 1;heap.push({v[i],i});}while (k--) {FLAG:auto t = heap.top(); heap.pop();if (t.first != v[t.second]) {heap.push({ v[t.second],t.second });//如果出现了元素对不上goto FLAG; //就返回去重新取}else {l[r[t.second]] = l[t.second];r[l[t.second]] = r[t.second];v[l[t.second]] += v[t.second];v[r[t.second]] += v[t.second];}}for (int i = r[0]; i != n+1; i = r[i]) {cout << v[i] << " ";}return 0;
}