题目描述

难度分:$1700$

输入$T( \leq 10^4)$表示$T$组数据。所有数据的$a+b+c$之和$\leq 3 \times 10^5$。

每组数据输入$a,b,c(0 \leq a,b,c \leq 10^5$且$1 \leq a+b+c)$。

有一棵二叉树，其中$a$个节点有两个儿子，$b$个节点有一个儿子，$c$个节点没有儿子。输出这棵二叉树的最小高度。

注意这里的高度是根到最远叶节点的路径上的边的个数。特别地，只有一个节点的二叉树的高度为 0。

输入样例

10
2 1 3
0 0 1
0 1 1
1 0 2
1 1 3
3 1 4
8 17 9
24 36 48
1 0 0
0 3 1

输出样例

2
0
1
1
-1
3
6
-1
-1
3

算法

贪心

这个题看着就感觉有$O(1)$的数学解法，但是思考起来不是特别容易想清楚，所以赛场上比较保守的做法还是用小根堆进行贪心。首先做个过滤，当$c \neq a + 1$的时候无解，输出$-1$，其余情况都有解。

贪心的策略就是尽量往深度最小的位置追加节点，首先将深度$0$加入到一个小根堆中，然后按以下步骤进行贪心：

1. 考虑度为$2$的节点，一共有$a$个这样的节点，考虑$a$次。每考虑一个节点的时候就弹出堆顶的深度$d$，此时这个度为$2$的节点会产生两个深度为$d+1$的节点，将两个$d+1$加入到小根堆中。
2. 考虑度为$1$的节点，一共有$b$个这样的节点，考虑$b$次。每考虑一个节点的时候就弹出堆顶的深度$d$，此时这个度为$1$的节点会产生一个深度为$d+1$的节点，将$d+1$加入到小根堆中。

由于肯定有解，我们不需要考虑$c$的约束，最后看看小根堆中的深度最大值，这个最大值就是我们要求的最小树高。

复杂度分析

时间复杂度

过一遍度为$2$的节点和度为$1$的节点需要遍历$a+b$次，如果$n=a+b+c$，在极限情况下$b=0$，整棵树是一个满二叉树，$a$和$c$的量级都为$O(\frac{n}{2})$规模，即$O(n)$。而每次都需要往小根堆插中入元素，时间复杂度为$O(log_2n)$。因此，整个算法的时间复杂度为$O(nlog_2n)$。

空间复杂度

空间复杂度由优先队列的消耗决定，在极限情况下$b=0$，会往小根堆中加入$a$个元素，是$O(n)$规模的元素数量。因此，算法的额外空间复杂度为$O(n)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
typedef pair<int, int> PII;
int T, a, b, c;

int main() {
    scanf("%d", &T);
    while(T--) {
        // a个节点有两个孩子，b个节点有一个孩子，c个叶子节点
        scanf("%d%d%d", &a, &b, &c);
        if(c != a + 1) {
            puts("-1");
            continue;
        }
        priority_queue<int, vector<int>, greater<int>> heap;
        heap.push(0);
        for(int i = 1; i <= a; i++) {
            int d = heap.top();
            heap.pop();
            heap.push(d + 1), heap.push(d + 1);
        }
        for(int i = 1; i <= b; i++) {
            int d = heap.top();
            heap.pop();
            heap.push(d + 1);
        }
        int ans = 0;
        while(!heap.empty()) {
            ans = max(ans, heap.top());
            heap.pop();
        }
        printf("%d\n", ans);
    }
    return 0;
}