Advertisement

UVa 12166优化天平(Equilibrium Mobile)

阅读量:

给定一棵深度不超过16的二叉树,其结构表示一个天平。每根杆均悬挂于中间位置,每个秤砣的重量均已知。请问至少需要调整多少个秤砣才能使天平达到平衡状态?

要点:

  • 或许有人会认为,只需每次记录天平左侧与右侧的数值,若两者不相等,则将需要修改的数目加一。然而这种方法并不正确,样例一已对此进行了说明。是否可以尝试保存一些可能的数值?这一思路或许具备可行性(有兴趣的朋友可以尝试实现)。
  • 然而实际上,一旦确定某个节点的重量,整个天平的状态也随之固定。由于该天平为完全二叉树结构,只要知道某一节点的重量,并结合其所在深度信息,即可推算出整个天平的总重量,即根节点所对应的重量值。因此可以通过遍历所有节点来计算总重量,并统计出现次数最多的总重量值。最终所需的修改数目等于节点总数减去该最大出现次数。
  • 此外还涉及到递归遍历的方法进行处理
复制代码
    #include<bits/stdc++.h>
    #define LL long long
    using namespace std;
    
    string s;
    LL len;
    LL cnt;
    unordered_map<LL, LL> m;
    
    void dfs(int depth) {
    	char ch;
    	if (cin.peek() == '[

全部评论 (0)

还没有任何评论哟~