Codeforces 1329C – Drazil Likes Heap(堆+贪心)
- 2020 年 4 月 5 日
- 笔记
题意
给出一个高度为 h 的大根堆, 要求弹出其中若干个数后高度变为 g, 并且前后大根堆都是满二叉树. 问新的大根堆所有数之和的最小值, 并要给出一种弹出数的操作序列(节点序号). h, g ≤ 20. 堆的弹出过程见如下代码:
题解
考虑新堆的每个节点的可能最小结果: 如果是叶子节点, 那么最小是取它的子树中最小的数; 否则, 取子树中比两个儿子大的数中的最小值.
那么, 能否能得到这个每个节点都取到最小值的堆呢, 回答是肯定的. 我们在得知哪些数字会留下后, 是要把其他点弹出的. 弹出这些数后, 我们还需要考虑新堆是不是满二叉树. 按序号从小到大考虑每个节点, 会发现(这个过程不太好描述, 主要还是堆的性质)每个节点最后的结果一定是以它为根的子树中剩余数字的最大值(被祖先节点使用的话是要移除的), 既然每个节点都有数字, 这个堆自然是满二叉堆.
要得到新堆的每个节点的数字, 可以从下到上维护每个节点的子树的序列. 每次合并都是 O(len) (len为序列长度) 的, 总的时间复杂度为 O(nlogn). 要输出操作序列时, 可以从下往上弹出不需要的数字, 这样不会影响到祖先的结构.
代码
#include <bits/stdc++.h> using namespace std; #define ll long long #define inc(i, l, r) for (int i = l; i <= r; i++) #define dec(i, l, r) for (int i = l; i >= r; i--) const int maxn = (1 << 20) + 5; int t, h, g; int val[maxn], nxt[maxn]; vector<int> sub[maxn]; inline vector<int> Merge(vector<int> v1, vector<int> v2, int id) { int sz1 = v1.size(), sz2 = v2.size(); vector<int> r(sz1 + sz2 + 1); for (int i = 0, j = 0; i + j < sz1 + sz2;) { if (j == sz2 || i < sz1 && v1[i] < v2[j]) { r[i + j] = v1[i]; i++; } else { r[i + j] = v2[j]; j++; } } r[sz1 + sz2] = val[id]; return r; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin >> t; while (t--) { cin >> h >> g; inc(i, 1, (1 << h) - 1) cin >> val[i]; inc(i, 1 << h - 1, (1 << h) - 1) sub[i] = vector<int>(1, val[i]); dec(i, (1 << h - 1) - 1, 1) { sub[i] = Merge(sub[i << 1], sub[i << 1 | 1], i); } set<int> s; ll sum = 0; inc(i, 1 << g - 1, (1 << g) - 1) { nxt[i] = sub[i][0]; s.insert(nxt[i]); sum += nxt[i]; } dec(i, (1 << g - 1) - 1, 1) { inc(j, 0, (int)sub[i].size() - 1) if (sub[i][j] > nxt[i << 1] && sub[i][j] > nxt[i << 1 | 1]) { nxt[i] = sub[i][j]; s.insert(nxt[i]); sum += nxt[i]; break; } } cout << sum << "n"; dec(i, (1 << h) - 1, 1) { if (s.find(val[i]) == s.end()) cout << i << " "; } cout << "n"; } } 
