首页 > 代码库 > 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 (二叉树结论)