首页 > 代码库 > UVa12166 Equilibrium Mobile (二叉树结论)

UVa12166 Equilibrium Mobile (二叉树结论)

2024-08-11 20:51:17   211人阅读

链接：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 (二叉树结论)






























        

            
                
                  
                
                

                    联系

                    我们