首页 > 代码库 > ZOJ 3805 Machine
ZOJ 3805 Machine
题目链接~~>
做题感悟:比赛时想到方法了,但是没能AC,很遗憾,没有考虑到左右子树的右节点相等的情况,结果就杯具了,比赛完后捋了一下思路就AC了,说明比赛时很不淡定,头脑不清醒,以后要注意。
解题思路:
题目给的就是一颗树,只是要把右节点多的放到左儿子上就好,这样减少个数,递归一下,注意左右儿子节点相等的情况需要加 1 。
代码:
#include<iostream> #include<sstream> #include<map> #include<cmath> #include<fstream> #include<queue> #include<vector> #include<sstream> #include<cstring> #include<cstdio> #include<stack> #include<bitset> #include<ctime> #include<string> #include<cctype> #include<iomanip> #include<algorithm> using namespace std ; #define INT __int64 #define L(x) (x * 2) #define R(x) (x * 2 + 1) const int INF = 0x3f3f3f3f ; const double esp = 0.0000000001 ; const double PI = acos(-1.0) ; const int mod = 1000000007 ; const int MY = (1<<5) + 5 ; const int MX = 100000 + 5 ; int n ; struct node { int le ,rt ; }T[MX] ; int dfs(int u) // 转变左右子树,计算有几个右儿子 { int Lson = 0 ,Rson = 0 ,num = 0 ; if(T[u].le) // 计算左子树 Lson = dfs(T[u].le) ; if(T[u].rt) // 计算右子树 Rson = dfs(T[u].rt) ; if(Lson < Rson) // 如果左子树的右儿子小于右子树的右儿子 swap(T[u].le ,T[u].rt) ; if(Lson == Rson) return Lson + 1 ; // 注意 return max(Lson ,Rson) ; } int main() { //freopen("input.txt" ,"r" ,stdin) ; int x ; while(~scanf("%d" ,&n)) { memset(T ,0 ,sizeof(T)) ; for(int i = 2 ;i <= n ; ++i) { scanf("%d" ,&x) ; if(T[x].le) T[x].rt = i ; else T[x].le = i ; } printf("%d\n" ,dfs(1)) ; } return 0 ; }
ZOJ 3805 Machine
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。