codeforces刷题日记

题目大意：要求你构造一棵树，树有三种节点，a个节点有两颗子树，b个节点有一颗子树，c给节点是叶子节点，求这样一颗树的最小深度。

思路：首先可以确定这是一颗二叉树，那我们可以先利用二叉树性质：a=c+1（可以想象一下，每次为一个叶子节点添加两条边，叶子节点+1，度为2的节点也+1；而为叶子节点只加一条边时，叶子节点数量不变），这样就可以判断题目给的节点数是否合理，不合理直接输出-1；只要合法了，那我们就不用管c了，因为根据a构建出来的二叉树一定c=a+1，我们要做的只要添加度为1和2的节点就可以，那如何让深度最小呢，那我们肯定要贪心的策略，尽可能先放度为2的，这样在一层的节点可以最多，在实现的时候，我们不需要创建一颗树，我们用curr和next保存当前深度和下一深度的节点树，然后迭代遍历即可。

#include<iostream>
using namespace std;
int t,a,b,c;
void solve() {int a, b, c;cin >> a >> b >> c;if (a + 1 != c) {cout << -1 << '\n'; return;}if (a + b + c == 1) {cout << 0 << '\n'; return;}int curr = 1, next = 0, res = 1;for (int i = 0; i < a + b; i++) {if (!curr) {swap(next, curr);res++;}curr--;next++;if (i < a) {next++;}}cout << res << '\n';
}
int main(){cin>>t;while(t--){solve();}return 0;
}