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)
还没有任何评论哟~
