首页 > 代码库 > UVa12166 Equilibrium Mobile (二叉树结论)
UVa12166 Equilibrium Mobile (二叉树结论)
链接:http://acm.hust.edu.cn/vjudge/problem/24840
分析:以二叉树的某个结点的重量为基准(基准的意思是它的重量不改变),要使整颗二叉树重量达到平衡,整棵树的总重量为w<<depth(w为基准重量,depth为结点的深度从0开始算)。那么统计出叶子结点的个数,并且算出以每个叶子结点的重量为基准时整棵树的总重量,把每种总重量出现的次数用map存起来,然后反过来想,要使整颗树在某个总重量下达到平衡,根据前面的(w<<depth)的推导,结点的深度和重量之间满足这样的一个关系,知道了其中两个就可以推出另一个,所以我们找出哪种总重量下的不需修改的叶子结点数最多,然后用总个数减去这个数就得到了最少需要修改的个数。
1 #include <iostream> 2 #include <string> 3 #include <map> 4 using namespace std; 5 6 typedef long long LL; 7 8 string expr; 9 map<LL, int> cnt;10 11 void dfs(int L, int R, int dep) {12 if (expr[L] == ‘[‘) {13 int p = 0;14 for (int i = L + 1; i <= R - 1; i++) {15 if (expr[i] == ‘[‘) p++;16 if (expr[i] == ‘]‘) p--;17 if (p == 0 && expr[i] == ‘,‘) {18 dfs(L + 1, i - 1, dep + 1);19 dfs(i + 1, R - 1, dep + 1);20 }21 }22 } else {23 LL w = 0;24 for (int i = L; i <= R; i++) w = w * 10 + expr[i] - ‘0‘;25 cnt[w << dep]++;26 }27 }28 29 int main() {30 int T;31 cin >> T;32 while (T--) {33 cnt.clear();34 cin >> expr;35 dfs(0, expr.size() - 1, 0);36 int sum = 0, maxx = 0;37 for (map<LL, int>::iterator it = cnt.begin(); it != cnt.end(); it++)38 sum += it -> second, maxx = max(maxx, it -> second);39 cout << sum - maxx << endl;40 }41 return 0;42 }
UVa12166 Equilibrium Mobile (二叉树结论)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。