cf1330 E. Drazil Likes Heap（贪心）

https://codeforces.com/contest/1330/problem/E

题意：

有一个高度为 \(h\) 的满大根堆，也就是有 \(2^h-1\) 个结点的满二叉树，父结点的值总大于两个子结点的值。结点的值两两不同，且从上到下、从左到右编号为 \(1\sim 2^h-1\) 。定义一种 “删除” 操作：

如果结点 \(i\) 没有儿子，删除 \(i\) ，即令 \(a[i] = 0\)；否则，递归删除值较大的儿子。

现要删去 \(2^h-2^g\) 个结点，使其变成高度为 \(g\) ，结点数为 \(2^g-1\) 的满二叉树。输出一种删点方案，使新树的所有结点值之和最小。

思路：

删除实际上是找一条连接 \(i\)、\(i\) 的大儿子、大儿子的大儿子…… 的链，把这条链整体上移一位，链的末尾位置置0，也就相当于删去链的末尾。从小到大遍历编号，如果从 \(i\) 开始的链的末尾位置的编号（用\(get\_id\)函数求出）超过了新树的范围就一直删

#include 
using namespace std;
#define ls(x) (x<<1)
#define rs(x) ((x<<1)|1)

const int N = (1<<21)+10;
int ans[N], a[N]; //树

void del(int i)
{
    if(!a[ls(i)] && !a[rs(i)])
        a[i] = 0;
    else if(a[ls(i)] > a[rs(i)])
        a[i] = a[ls(i)], del(ls(i));
    else
        a[i] = a[rs(i)], del(rs(i));
}

int get_id(int i)
{
    if(!a[ls(i)] && !a[rs(i)])
        return i;
    if(a[ls(i)] > a[rs(i)])
        return get_id(ls(i));
    else
        return get_id(rs(i));
}

signed main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T; cin >> T; while(T--)
    {
        int h, g; cin >> h >> g;
        //注意初始化，要把后面的点置0
        fill(a+(1<> a[i];

        int cnt = 0;
        for(int i = 1; cnt < (1< (1<