寂寞花开
寂寞沙茶不知味
posts - 2,comments - 2,trackbacks - 0

额,这题其实挺简单,练手了。
题目大意:
  给你一棵树,问这棵树能否经过调整后变成完全二叉树。
  这棵二叉树满足叶子节点的深度差<=1。
解法:
  首先,先遍历一遍这棵树,保留d[i]表示第i号节点到顶点的距离,s[i,1..2]表示i节点左右儿子的叶子节点总数,h[i,1..2]表示i节点左右儿子节点的最深深度。
  好了,那么如果某个节点左右儿子节点的深度差大于1那么肯定无解。
  如果某一层的最后儿子深度差等于1的节点数>1那么肯定无解。
  很显然的吧。
  然后就是调整,按先序遍历,s[i,1]<s[i,2]就交换,总次数+1,最后就是结果。
  很简单吧,程序86行:

{$M 10000000}
program mobiles;
 var f
,d:array[-1..100001] of longint;
     son
,h,s:array[-1..100001,1..2] of longint;
     sum
:array[0..100] of longint;
     n
,num:longint;
 {
---------------------------------------------------}
 procedure init;
  var i
,p,q:longint;
  begin
   readln(n);
   
for i:=1 to n do
    begin
     readln(p
,q);
     
if p<>-1 then f[p]:=i; son[i,1]:=p;
     
if q<>-1 then f[q]:=i; son[i,2]:=q;
    end;
  end;
 {
---------------------------------------------------}
 function max(x
,y:longint):longint;
  begin
   
if x>y then exit(x);
   
exit(y);
  end;
 {
---------------------------------------------------}
 function min(x
,y:longint):longint;
  begin
   
if x<y then exit(x);
   
exit(y);
  end;
 {
---------------------------------------------------}
 procedure dfs(x
:longint);
  var i
:longint;
  begin
   d[x]
:=d[f[x]]+1;
   
for i:=1 to 2 do
   
if son[x,i]=-1 then begin
    h[x
,i]:=1;s[x,i]:=1; end
    
else begin
     dfs(son[x
,i]);
     h[x
,i]:=max(h[son[x,i],1],h[son[x,i],2])+1;
     s[x
,i]:=s[son[x,i],1]+s[son[x,i],2];
     end;
  end;
 {
---------------------------------------------------}
 procedure nosol;
  begin
   writeln(
-1);
   
close(output);
   halt;
  end;
 {
---------------------------------------------------}
 procedure update(x
:longint);
  var i
:longint;
  begin
   
if x=-1 then exit;
   
if s[x,1]<s[x,2] then
    begin
     i
:=son[x,1];son[x,1]:=son[x,2];son[x,2]:=i;
     inc(num);
    end;
   update(son[x
,1]);
   update(son[x
,2]);
  end;
 {
---------------------------------------------------}
 procedure main;
  var i
:longint;
  begin
   dfs(
1);
   
for i:=1 to n do
    
if abs(h[i,1]-h[i,2])>1 then nosol
    
else 
    
if abs(h[i,1]-h[i,2])=1 then inc(sum[d[i]]);
    
for i:=1 to 100 do
     
if sum[i]>1 then nosol;
   update(
1);
   writeln(num);
  end;
 {
---------------------------------------------------}
 begin
  assign(input
,'mobiles.in');reset(input);
  assign(output
,'mobiles.out');rewrite(output);
  init;
  main;
  
close(output);
 end
.

居然没有Pascal,我去学c++吧
posted on 2010-04-24 16:30 一芥书生 阅读(243) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理