额,这题其实挺简单,练手了。
题目大意:
给你一棵树,问这棵树能否经过调整后变成完全二叉树。
这棵二叉树满足叶子节点的深度差<=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 @
2010-04-24 16:30 一芥书生 阅读(243) |
评论 (0) |
编辑 收藏
原来随笔才能发到首页上,刚知道。
posted @
2010-04-24 14:52 一芥书生 阅读(146) |
评论 (0) |
编辑 收藏