ACPC 2014 G. Special Christmas Tree
题目描述:
在保证所有叶子节点都挂礼物(礼物总数为L)且二叉树的高度不超过H的情况下,二叉树最多能有几个结点?
解题思路:
这道题从叶子结点的个数来入手,因为最后我们的二叉树显然是H的高度,我们不妨一层一层的来看,如果当前层的叶子结点小于等于礼物数量的话,就加上这一层,如果当前层的叶子结点数目大于礼物数量的话,这一层只能由L个,后面的(H-i)层也只能由L个。
代码:
#include<bits/stdc++.h> using namespace std; typedef long long ll; int main() { ll T, H, L, cnt = 0; cin >> T; while(T--) { cin >> H >> L; ll ans = 0; for(int i = 0; i < H+1; ++i) { if(1 << i >= L) { ans += (H - i + 1) * L; break; } else { ans += (1 << i); } } printf("Case %lld: %lld\n",++cnt,ans); } }