TYVJ P2064(点的向下维护）
TYVJ P2064(点的向上维护）
P2064 - 「Poetize10」能量获取From lydliyudong Normal (OI)总时限：10s 内存限制：128MB 代码长度限制：64KB |
||||||
|---|---|---|---|---|---|---|
|
||||||
此题贪心 贪最小的点，易证必最优解
Program energy;
const
maxn=1000;
var
n,i,j,ans:longint;
f,e,w,num,hpos:array[0..maxn] of longint;
procedure swap(var a,b:longint);
var
t:longint;
begin
t:=a;a:=b;b:=t;
end;
function max(a,b:longint):longint;
begin
if a>b then exit(a) else exit(b);
end;
function min(a,b:longint):longint;
begin
if a<b then exit(a) else exit(b);
end;
procedure qsort(l,r:longint);
var
i,j,m,p:longint;
begin
i:=l;
j:=r;
m:=e[(l+r) div 2];
repeat
while (e[i]<m) do inc(i);
while (e[j]>m) do dec(j);
if (i<=j) then
begin
swap(e[i],e[j]);
swap(f[i],f[j]);
swap(w[i],w[j]);
swap(num[i],num[j]);
inc(i);dec(j);
end;
until i>j;
if (l<j) then qsort(l,j);
if (i<r) then qsort(i,r);
end;
procedure pour(x:longint);
var
noww,i,j:longint;
begin
noww:=maxlongint;
i:=x;
while (i<>0) do
begin
noww:=min(noww,w[i]);
i:=hpos[f[i]];
end;
if (noww<e[x]) then exit;
inc(ans);
i:=x;
while (i<>0) do
begin
dec(w[i],e[x]);
i:=hpos[f[i]];
end;
end;
begin
readln(n);
for i:=1 to n do
begin
read(f[i],e[i],w[i]);
num[i]:=i;
end;
qsort(1,n);
hpos[0]:=0;
for i:=1 to n do hpos[num[i]]:=i;
// for i:=1 to n do write(f[i],' ',e[i],' ',w[i]);
ans:=0;
for i:=1 to n do pour(i);
writeln(ans);
end.